行业研究报告哪里找

华为技术有限公司深圳市龙岗区坂田华为总部办公楼电话： 86 755 28780808邮编：518129免责声明本资料可能含有预测信息，包括但不限于有关未来的财务、运营、产品系列、新技术等信息。由于实践中存在很多不确定因素，可能导致实际结果与预测信息有很大的差别。因此，本资料信息仅供参考，不构成任何要约或承诺，华为不对您在本资料基础上做出的任何行为承担责任。华为可能不经通知修改上述信息，恕不另行通知。版权所有 2022 华为技术有限公司，保留一切权利。非经华为技术有限公司书面同意，任何单位和个人不得擅自摘抄、复制本资料内容的部分或全部，并不得以任何形式传播。商标声明 和 是华为技术有限公司商标或者注册商标，在本资料中以及本资料描述的产品中，出现的其它商标、产品名称、服务名称以及公司名称，由其各自的所有人拥有。、操作系统演进：历史、现在与展望 第1页MindSpore：人工智能开源生态系统实践 第18页技术使能艺术：新一代HDR Vivid视频技术标准 第122页2022年12月第 3 期（总第3期）内部资料 免费交流准印证号：（粤BL）022060040Communications of HUAWEI RESEARCH华为研究内部资料，免费交流准印证号：（粤BL）022060040主编：廖恒本期责任主编：陈海波，陆品燕编委会：廖恒，童文，肖新华，胡邦红，周慧慧，鲍丰，Jeff Xu，陈海波，陆品燕，张小俊，李瑞华，白博索阅、投稿、建议和意见反馈，请联系：HWR印刷数量：4000本印刷单位：雅昌文化（集团）有限公司印刷地址：深圳市南山区深云路19号印刷日期：2022年12月16日版权所有 2022 华为技术有限公司，保留一切权利。华为研究内部资料，免费交流准印证号：（粤BL）022060040主编：廖恒本期责任主编：陈海波，陆品燕编委会：廖恒，童文，肖新华，胡邦红，周慧慧，鲍丰，Jeff Xu，陈海波，陆品燕，张小俊，李瑞华，白博索阅、投稿、建议和意见反馈，请联系：HWR印刷数量：4000本印刷单位：雅昌文化（集团）有限公司印刷地址：深圳市南山区深云路19号印刷日期：2022年12月16日版权所有 2022 华为技术有限公司，保留一切权利。编者按陈海波华为基础软件首席科学家陆品燕华为理论计算机首席科学家欢迎大家来到华为研究软件与理论分册！软件正在重塑数字世界与物理世界，成为数字世界的核心基础设施。如何构建软件基础能力并突破软件核心技术，是现代企业乃至国家拥抱数字世界的核心抓手。与物理世界的对象不同，软件是一种“看不见摸不着”的逻辑实体，可能也是人类迄今为止所设计的最复杂的系统，一个大型软件系统的代码往往可达数亿行。软件的发展有其客观规律，不存在一劳永逸的“银弹”。软件包含基础软件、应用软件与工具软件等不同类型，面向智能终端、嵌入式设备、云与企业 IT 等诸多产业，它们的发展规律各具特色，生态现状与需求也存在差异。软件的生命周期与供应链管理具有自身的独特性，支撑软件不断发展的软件理论也在不断演进。研究与掌握这些规律和理论，是我们研发出好软件的关键。华为公司长期以来在软件与理论领域持续投入，不仅面向终端、联接、计算、云与智能驾驶等多产业构筑了良好的竞争力，通过可信及软件工程变革不断提升软件的工程与可信能力，还构建了欧拉和鸿蒙两大操作系统生态，从而推动了openEuler、OpenGuass、MindSpore、OpenHarmony 等基础软件开源社区的建设。本分册汇聚了华为公司在基础软件、软件理论以及开源社区构建等领域的专家观点与新近成果。在基础软件领域，操作系统演进：历史、现在与展望从产业应用演进与硬件演进两个维度来分析操作系统发展轨迹、创新机遇与技术挑战，并介绍 openEuler 和 OpenHarmony 在技术演进方面的实践；GaussDB：云原生分布式数据库介绍了中央软件院高斯部开发的企业级分布式数据库平台 GaussDB Kernel，以及该平台的架构和主打特性；MindSpore：人工智能开源生态系统实践介绍了深度学习框架 MindSpore 的主要架构与核心技术，以及在人工智能开源生态系统方面的实践探索；华为毕昇编译器的创新与实践在总结分析编译器技术演进的基础上，系统性地介绍了华为毕昇编译器的技术创新与实践，分析核心技术特性，并阐述了进一步演进和创新的技术方向。在软件理论领域，在线匹配领域的最新进展介绍了在线匹配技术的最新学术进展；面向组合优化的学习增强算法设计介绍了在组合优化中运用 AI 技术的新近学术成果；求解器是一类非常重要的工具软件，也是工业软件的核心基础，随机游走与适应度函数相结合求解布尔可满足性问题介绍了随机游走技术在 SAT 求解器算法中的重大突破；域理论是编程语言及其分析工具最早的数学理论基础，域理论与交互式计算是一篇综述文章，详细介绍了域理论自上世纪六十年代以来的发展历史，以及在编程模型不断演进的过程中，如何被用于刻画交互、并发等行为。“软件吞噬一切，开源吞噬软件”，开源策略的制定与社区构建的度量从企业开源策略的制定和企业开源社区的构建等方面阐述了企业如何利用开源发展生态经济，并推动产业数字化转型。本分册还有很多优秀文章，内容面向软件领域的关键挑战，力求贴近产业热点，希望对读者有所启发。不当之处，也请多多批评指正！0112183748587910211312289基础软件软件理论软件技术与生态操作系统演进：历史、现在与展望陈海波，钱梽杨，贾宁，胡欣蔚，李毅GaussDB：云原生分布式数据库Andy Li，任阳MindSpore：人工智能开源生态系统实践于璠，时北极，王紫东，金学峰，陈雷，苏腾，李锐锋，周斌，丁诚，谭焜华为毕昇编译器的创新与实践高耀清，华保健 在线匹配领域的最新进展唐志皓，张宇昊面向组合优化的学习增强算法设计黄棱潇，王彧弋，阎翔随机游走与适应度函数相结合求解布尔可满足性问题蔡少伟，姜滔域理论与交互式计算Glynn Winskel智能汽车LiDAR辅助GNSS-RTK定位 Han Gao，Weisong Wen，Li-Ta Hsu，Yongliang Wang技术使能艺术：新一代HDR Vivid视频技术标准余全合，徐巍炜，王弋川，张继武，陈虎，袁乐开源策略的制定与社区构建的度量侯培新，李自，王晔晖0112183748587910211312289基础软件软件理论软件技术与生态操作系统演进：历史、现在与展望陈海波，钱梽杨，贾宁，胡欣蔚，李毅GaussDB：云原生分布式数据库Andy Li，任阳MindSpore：人工智能开源生态系统实践于璠，时北极，王紫东，金学峰，陈雷，苏腾，李锐锋，周斌，丁诚，谭焜华为毕昇编译器的创新与实践高耀清，华保健 在线匹配领域的最新进展唐志皓，张宇昊面向组合优化的学习增强算法设计黄棱潇，王彧弋，阎翔随机游走与适应度函数相结合求解布尔可满足性问题蔡少伟，姜滔域理论与交互式计算Glynn Winskel智能汽车LiDAR辅助GNSS-RTK定位 Han Gao，Weisong Wen，Li-Ta Hsu，Yongliang Wang技术使能艺术：新一代HDR Vivid视频技术标准余全合，徐巍炜，王弋川，张继武，陈虎，袁乐开源策略的制定与社区构建的度量侯培新，李自，王晔晖01|华为研究2022 年 12 月基础软件操作系统承上启下，向上服务应用，向下管理与挖潜硬件能力，是构建硬件生态与应用生态的关键。本文分别从产业与应用演进和硬件演进两个维度来分析其发展轨迹、创新机遇与技术挑战，并介绍 openEuler 和 OpenHarmony 的实践。关键词操作系统，openEuler，OpenHarmony摘要陈海波 1，钱梽杨 1，贾宁 1，胡欣蔚 1，李毅 21中央软件院2 终端 BG 软件部操作系统演进：历史、现在与展望华为研究|022022 年 12 月图 1 操作系统在整个计算系统中的定位图 2 操作系统与产业应用的共生发展历史1 引言按照 计算机科学技术百科全书（第三版）1的定义，操作系统是“管理硬件资源、控制程序运行、改善人机界面和为应用软件提供支持的一种系统软件”。操作系统自诞生以来，其内涵与外延一直在不断扩大，早期的操作系统只包含操作系统内核与原始的 Shell（如命令行终端），现代操作系统的功能不断扩大，包含了扩展操作系统内核管理与抽象硬件资源功能的操作系统服务以及为应用创建执行环境与管理应用执行的应用框架（如图 1）。操作系统在整个计算系统中发挥“承上启下”的关键作用。承上就是为应用提供运行时和开发环境服务，并在一些场景下还作为应用生态与云服务的入口；启下则是高效、安全地管理硬件，最大程度地发挥硬件潜力，并使能硬件生态。本文将分别从产业与应用演进和硬件演进两个维度来观察和思考其发展轨迹，并从应用场景驱动与硬件驱动两个维度来展望操作系统发展方向。最后，本文将介绍openEuler 和 OpenHarmony 的创新实践。操作系统操作系统应用应用系统服务内核芯片和硬件芯片和硬件云服务云服务应用框架2 产业演进中的操作系统2.1 操作系统伴随产业浪潮诞生与发展回顾操作系统的发展史（见图 2），在业界取得成功的操作系统通常都是伴随着产业浪潮诞生与发展的，并与产业互相促进。在早期的计算机中软件硬件深度耦合，从而使得应用程序开发的专业性高、开发效率低，对更方便地使用计算机并进行应用开发的需求直接推动了编程语言和操作系统的诞生，也使得软硬件持续解耦。1956 年诞生的 GM-NAA I/O 2 系统可以被称为操作系统的雏形，主要提供了输入和输出的管理系统。直到20 世纪 60 年代，才形成了真正意义上的操作系统。在此之前，大型机的软件与硬件深度耦合，软件往往需要等待硬件研制后数年才得以研发成功上市，从而影响整体系统的上市节奏。1964 年，IBM 发布的 OS/360 3 首次推动了软件与硬件解耦；并且，这一操作系统的复杂研制过程还催生了“软件工程”学科的开创性书籍人月神话：软件项目管理之道4，该书对今天我们认识软件的复杂性仍然具有很强的现实指导意义。1969 年，贝尔实验室的 Ken Thompson 和 Dennis Ritchie 在参加多任务信息与计算系统（Multiplexed Information and Computing Service，Multics）5 的研究后，认为这一系统过于复杂，从而在简化 Multics 系统的设计理念的基础上研制了 Unix 操作系统（原本叫 Unics，其中的 Uni-与 Multics 中 Multiplexed对应）6；基于此操作系统的理念，诞生了后续包括 Linux在内的一系列操作系统。20 世纪 80 年代面世的一系列操作系统，推动了小型机到 PC 机和嵌入式的演进与发展。举例而言，QNX 7诞生于 1982 年，广泛应用于嵌入式领域，当前在智能车领域被广泛应用；VxWorks 8 诞生于 1982 年，主要在嵌入式和工业场景广泛使用；Windows 的诞生则推动了 PC的发展，并在随后的 30 多年时间里始终在个人电脑和 PC服务器市场上占据主流地位；此外，前文提及的 1991 年诞1980s1980s1990s1990s2010s2010sPC&嵌入式PC互联网移动互联网万物智联2020s2020s联接数：1000亿用户数：10亿 用户数：30亿 用户数：40亿 QNX/QNX/VxWorksVxWorks(1982)(1982)Windows(1985)Windows(1985)主机用户数：数万 OS/360(1964)OS/360(1964)Unix(1969)1960s1960s iOSiOS(2007)(2007)Android(2008)Android(2008)？Linux(1991)Linux(1991)03|华为研究2022 年 12 月基础软件生的 Linux 系统，推动了 PC 服务器和云计算的发展。iOS 和 Android 等移动操作系统的诞生则推动了手机等移动设备从功能机走向智能机，并伴随着移动互联网的发展，成为移动互联网时代的王者。面向未来，随着信息技术（Information Technology，IT）、通信技术（Communication Technology，CT）和运营技术（Operational Technology，OT）的逐步融合，以及人工智能（Artificial Intelligence，AI）与 5G 等技术的发展，操作系统将迎来万物智联的新发展机遇与挑战。2.2 操作系统的成功要素也伴随着产业不断演进操作系统所承载的价值和成功要素也在不断演进，大致经历了硬件附属、作为独立的软件产品、作为生态与云服务入口以及赋能和赋智千行百业等阶段（见图 3）。早期的操作系统（IBM OS/360 和早期的 Unix 等）作为硬件的附属品，其价值也依附于硬件的价值产生。例如，IBM OS/360 作为 IBM 大型机的附属而体现其价值。彼时，硬件设备性能约束大，在这个阶段的操作系统关键的成功要素是性能。硬件附属硬件附属独立的软件产品独立的软件产品生态入口生态入口 云服务云服务赋能、赋智千行百业赋能、赋智千行百业1960s1960sOSOS的的价值价值年代年代1980s1980s2000s2000s2020s2020s例如：IBM OS/360和Unix例如：Windows例如：Android GMS成功要素：性能成功要素：通用成功要素：粘性成功要素：柔性、智能图 3 操作系统的价值与成功要素演进20 世纪 80 年代以来，操作系统逐步成为一个独立的软件产品。例如，Windows 就是这一阶段作为独立的软件产品销售的典型代表。由于软件的可复制性非常强，销售软件授权（License）可以获得巨大价值，这使得微软在很长一段时间内都是市值最高的 IT 公司之一。这一阶段，操作系统获得成功的关键要素是通用。Windows 对设备的兼容性和应用的通用性，推动了 PC 时代的发展。2000 年以后，操作系统的商业模式逐步演进为作为生态与云服务的入口。例如苹果 iOS iCloud App Store与安卓 GMS 应用市场形式，通过提供一个生态入口，加上与云的连接，形成一个非常强大的生态，它的成功因素主要是生态的粘性。展望未来，随着数字世界进入每个人、每个家庭、每个组织，从而构建万物互联的智能世界，操作系统支撑这一战略的关键是要能够赋能、赋智各行各业，而其核心成功要素是柔性和智能。需要强调的是，上述四种模式并不是替代关系，而是逐步演进的，旧的模式在相当长的时期里会一直存在。面向未来，我们将看到多种形态的共存。例如，操作系统将持续支撑设备类产品的竞争力，操作系统作为生态与云服务入口的方式方兴未艾，同时业界也在积极探索如何赋能、赋智千行百业。华为研究|042022 年 12 月图 4 人机物融合与云网边端协同新使命 9图 5 硬件形态爆炸式地进化、杂交和演变面向未来赋能、赋智千行百业，终端、IT 与 CT 等技术逐步融合，从某种程度来讲，操作系统将承担起人机物融合以及云网边端协同的新使命（见图 4）。封闭场景下的操作系统所面对的往往是物理资源安全的、静态孤立的网络域，适用小规模抽样数据分析，整体是一个静态、封闭、受限的系统。而面向千行百业，操作系统从一个静态、封闭、受限的系统演进到一个动态、开放、扩展的系统，适用全样本大规模的数据分析，需要更加关注虚拟资源的安全 9。3 业务场景驱动的操作系统创新方向展望3.1“昆虫纲悖论”呼唤元 OS 架构创新万物智联会带来许多新的变化，其中一个显著变化就人机物人机物融合融合态势态势静态、封闭、受限的系统静态、封闭、受限的系统小规模抽样数据分析小规模抽样数据分析静态孤立网络静态孤立网络物理资源安全物理资源安全动态、开放、扩展的系统动态、开放、扩展的系统全样本大规模数据分析全样本大规模数据分析移动泛在互联网移动泛在互联网虚拟资源安全虚拟资源安全主机台式机1960s1960s1980s1980s2000s2000s2020s2020s是产品和应用场景会呈现爆炸式地形态进化、杂交和不断演进。我们传统认知上的一种设备，跟其他设备进行杂交、融合，就可能会诞生出新的硬件形态，并增加原有硬件的附加值（见图 5）。“昆虫纲悖论”是东京大学的坂村健教授对个性化与通用性之间矛盾提出的一个形象比喻。地球上的哺乳动物大约有 5 千多种，好比传统的服务器、PC 和手机等设备；昆虫大概有 100 多万种，好比万物智联时代的多样化设备。一方面，数量更大的万物智联设备带来的累计价值，可能会超过 PC 和手机市场；但另一方面，由于缺乏可大批量复制的软硬件和应用，没有批量也就难以有低成本，因而很难产生很大的市场。面向万物智联时代的硬件形态不断创新，会带来操作系统的“昆虫纲悖论”挑战，亟需应对多样化场景下的资源大小、功能、性能、安全、生态等多方面的差异化。操作系统必须实现组件式解耦与按需合成，既能够保证架构的一致05|华为研究2022 年 12 月基础软件性，便于统一维护，同时可以通过弹性组合的方式去解决个性问题。我们将满足这样设计意图的操作系统架构称为“元OS 架构”。元 OS 架构的目标是“One OS Kit for All”，即我们要打造的不再只是一个操作系统，而是一个可以被灵活组装的操作系统能力集合（OS Kit），基于一个高度弹性的架构，将这些操作系统能力组合成为满足各行各业场景需要的场景化操作系统，进而缓解“昆虫纲悖论”挑战。3.2 新形态计算呼唤操作系统诞生新的计算抽象回顾虚拟化和容器这两个当前主流的计算抽象的历史（见图 6），前者诞生于上世纪 70 年代，早在 IBM OS/370 就已提供了虚拟化能力，而创立于 1998 年的VMware 则开启了 PC 服务器虚拟化的时代序幕；后者在上世纪 70 年代也出现了雏形，比如，早在 1979 年 Unix V7 就提供了早期的隔离环境，而现在业界主流的 Linux 容器（Linux Container，LXC）诞 生 于 2008 年，Docker则诞生于 2013 年。虚拟化和容器在一定程度上使能了云计算革命。然而，随着函数计算、边缘计算的兴起，虚拟机和容器这样的计算抽象存在一定的局限性。以函数计算为例，对运行时环境的新诉求逐步突显，包括（但不仅限于）：75%的函数计算的最大执行时间仅为 10 秒，希望运行时环境具备极致轻量化和超短生命周期能力；81%的函数计算为低频调用(平均每分钟少于 1 次），要求更高效地减少驻留内存，提升资源利用率；传统的分支预测在面对短函数时错误率非常高，呼吁打造更有效的新型调度机制；场景更加开放，对安全隔离的诉求更高等 10。这些对操作系统的新诉求与传统操作系统的差异非常大，虚拟机和容器的抽象显得过于厚重，安全隔离性也存在可提升的空间。以上新形态计算诉求正在呼唤操作系统领域诞生新的运行时抽象。3.3 系统的复杂性和敏捷性之间的矛盾逐步催生“学习型系统”系统的复杂性和敏捷性之间的矛盾催生“Learned Systems”，即 AI 与系统相结合。在封闭系统下，过去的操作系统是一个结果确定的、整体等于部分之和、稳定封闭的操作系统，因此适用基于经验的调优；然而，面向一个开放、成长的复杂系统，它的整体可能会大于部分总和，而且会不断演化，因此更适合用 Learning 的方式提升系统效率9（见图 7）。然而，用机器学习或者用 AI 来解决系统问题，需要思考如何把机器学习的方式和传统的基于经验的或者基于系统设计的方式，进行有效结合，才能发挥学习型系统的优势。图 6 操作系统运行时抽象的演进图 7 还原论与系统论的差别 91970s1970s1980s1980s1990s1990s2000s2000s2010s2010s2020s2020s大型机（Mainframe）虚拟化小型机（Unix）虚拟化PC服务器虚拟化（VMware/Xen/KVM）容器（LXC/Docker）?稳定封闭的稳定封闭的系统系统整体等于部整体等于部分之和分之和结果确定性结果确定性开放成长的开放成长的复杂系统复杂系统整体大于部整体大于部分之和分之和关联演化关联演化还原论还原论系统论系统论华为研究|062022 年 12 月图 8 算力演进示意图操作系统的参数数量庞大、业务负载与系统状态瞬息万变，如何实现自动调优和运维是业界面临的普遍挑战，也是学术界的研究热点。近年来，学术界在该领域也不断取得新的研究进展，包括（但不仅限于）：基于学习的操作系统 11、基于学习的可扩展索引 12、基于学习的缓存 13与基于学习的并发控制 14 等。4 硬件驱动的操作系统创新方向展望4.1 异构众核 SoC、XPU 协同和新计算架构演进呼唤新的计算范式从算力的角度看，操作系统需要协同和推动异构众核片上系统（System on a Chip，SoC）、XPU 协同和新计算架构三大方面的计算范式演进（见图 8）。异构众核 SoC：CPU 从单核、多核演进到了当前的众核，在服务器场景下已经可见数百核，甚至千核的规模；同时，我们观察到大小核/异构核也从过去的手机等终端设备，进入到 PC 场景（例如苹果 M1），并且有演进到服务器的趋势。围绕异构众核 SoC，操作系统需要研究诸多挑战性的课题，包括但不仅限于：合成大规模的可扩展同步原语 15、提升同步CPUDRAM闪存/硬盘以以CPUCPU为中心为中心DPUGPUGPUDPUNPUCPUNPUCPU以数据为中心 DRAM SCM NAND HDDDSADSA单核 多核 众核众核 异构众核异构众核XPUXPU算力协同算力协同新计算架构新计算架构原语的可靠性和可扩展性以便能够可靠地释放并发算力 16、非统一内存访问（Non-uniform Memory Access，NUMA） 非 对 称 多 处 理（Asymmetric Multiprocessing，AMP）架构感知和瞬态线程迁移等。领域专属架构（Domain-Specific Architecture，DSA）下的 XPU 算力协同：操作系统需要突破 XPU（例如CPU、GPU、NPU、DPU等）间的高效协同，从过去的单一操作系统演进为 SoC 上的一组协同的操作系统，从而最大程度地发挥 SoC 的整体能效。新计算架构探索：DSA 的弊端逐步显现，例如，厂家要看护多种硬件架构、功能重叠浪费、软件栈难以共享、XPU 间协同调度效率难以大幅提升等。牧村定律 17认为半导体技术每十年完成一次定制化和通用化的回归。业界也期待 DSA 之后能够诞生新的计算架构。而在新的计算架构下，传统操作系统的基础架构和基础能力也将发生根本性的变革。4.2 新存储介质和互联技术需要操作系统提供新的数据管理范式传统的缓存、内存、存储的速度与成本是泾渭分明的，它们以 CPU 为中心，形成了梯次缓存的多层存储结构。而存储级内存（Storage Class Memory，SCM）等非易失07|华为研究2022 年 12 月基础软件内存的出现，使得存储介质时延从毫秒级进入到微秒级（见图 9）；同时，结合 UB 等高性能、高可扩展性的新型互联技术出现 18（见图 10），传统的数据管理范式正在面临挑战。存储介质时延从毫秒级进入到微秒级，软件栈的时延在整个 I/O 中的占比呈数量级地提升，因此超低时延的存储软件栈 19、高并发下数据一致性 20 等成为近年的研究热点。在新介质与新互联技术的共同推动下，传统操作系统的内存和存储两层存储管理架构将可能逐步演进到以数据为中心的单级存储（Single-Level Store，SLS）架构，即内存和存储在逻辑层面上实现了融合管理，从而大幅减1 ns1 ns10 ns10 ns100 ns100 ns1 1 s10 10 s100 100 s1 1 msms10 10 msms100 100 msms1s1sSRAMSRAMDRAMDRAMNANDNANDHDDHDDTapeTapePM/SCMPM/SCM内存内存存储存储图 9 新介质正在使得内存与存储融合图 10 互联技术的性能与可扩展性图 11 操作系统计算架构与范式的演进趋势可扩展性性能RoCE/InfiniBandPCIe内存总线UBUB14224 Gbit/s14224 Gbit/s50 Gbit/s464 Gbit/s12.525 Gbit/s少数据搬移；进一步，如何使数据离计算节点更近，实现以业务为中心的效果？这也呼吁近数计算（Near Data Computing，NDC）系统的出现（见图 11）。4.3 机密计算架构呼唤操作系统领域研究新的信任范式“机密计算”（Confidential Computing）是指在可信硬件支持下的隔离环境中运行安全计算任务，从而实现对安全计算任务的代码和数据进行保护的一项安全技术。随着数据安全与隐私监管的不断加强（例如，欧盟的 GDPR、以及中国的数据安全法等），机密计算受到业界越来越多的关注。从 2002 年 ARM 提出 TrustZone 架构起，出现了各种机密计算技术方案和抽象演进（见图 12）21。TrustZone 是 ARM 在 2002 年提出的隔离机制，其隔离对象包含了 CPU、内存、总线结构和外围设备，提供了独立的物理机抽象 22。目前，TrustZone 在移动端ARM手机上被广泛部署和使用，提供生物信息识别（例如，指纹识别、人脸识别、虹膜识别）以及安卓系统密钥管理等安全特性。通常，在 ARM TrustZone 会运行一个小而安全的操作系统，例如，Huawei iTrustee 23、OP-TEE 24、Trustonic 25 等。DPUDPUGPUGPUGPUGPUDPUDPUNPUNPUCPUCPUNPUNPUCPUCPU新介质新介质SLSSLSCPUCPUDRAMDRAM闪存闪存/硬盘硬盘以以CPUCPU为中心的三层架构为中心的三层架构CPU 多层存储以数据为中心的以数据为中心的SLSSLSXPU 新介质架构以业务为中心的原位计算以业务为中心的原位计算面向业务的高质量数据划分面向业务的高质量数据划分按照数据应用特征进行均衡划分数据节点数据节点数据节点数据节点数据节点数据节点数据节点数据节点数据节点数据节点基于原位计算的事务处理框架基于原位计算的事务处理框架微秒级低时延数据迁移软硬协同的本地事务执行华为研究|082022 年 12 月图 12 机密计算主要技术及其发展历史2021 年 的 ARM Vision Day 上，ARM 发 布 了 新一代 ARM V9 架构，其中提出了 ARM 机密计算架构（Confidential Compute Architecture，CCA），在 原有的 Non-Secure World 和 Secure World（之前的可信执行环境，TEE）基础上，新引入一个安全区叫 Realm。CCA 新架构的本质是改变了信任范式，从此前终端领域的“信任设备，不信任应用”，演进到云计算领域的“客户信任自己的应用，但不必信任基础设施提供商”。操作系统需要支持 Realm Manager 以及其上的可信任操作系统，才能有效支撑 ARM CCA 的这一信任范式改变 26。2015 年，Intel 正式宣布软件防护扩展（Software Guard Extensions，SGX）技术并发布第一代 SGX。SGX在用户态进程中划分出一块安全“飞地”（Enclave），Enclave 内的代码和数据对外界完全不可见。程序员需要显式地对代码进行静态划分：安全部分（Enclave）与非安全部分（App），并规定好二者交互的接口。SGX 的安全威胁模型不信任操作系统，因此 SGX 在硬件设计中定义了大量功能，用于检验底层不可信特权软件的行为，主要包括安全页表管理、安全线程管理、安全内存的换页管理、以及安全内存的完整性校验等。由于 Enclave 抽象是应用的一部分，而应用与操作系统的接口与交互极其复杂并且经常演进，导致 SGX 的硬件设计比较复杂，硬件需要承载很多软件的功能，并且性能开销也较大。2022 年 1 月 Intel 宣布在除服务器之外的新桌面/笔记本/嵌入式处理器中放弃所有的 SGX 特性 27。信 任 域 扩 展（Trust Domain Extensions，TDX）是 Intel 继 SGX 之后推出的新安全计算抽象。在设计上，TDX 引入了单独的可信的 Hypervisor/VMM，和原有的云平台 VMM 共享同一物理主机。可信的 Hypervisor 称为TDX Module，是一小块安全模块，负责可信域（Trusted Domain，TD）内的可信虚拟机和外部不可信 VMM 之间的交互检查。从 ARM CCA 和 Intel TDX 等演进趋势看，操作系统领域需要研究相应的信任范式演进，通过创新操作系统的架构设计（例如，微内核架构）来减少机密计算抽象内的可信计算基（Trusted Computing Base，TCB）的大小，同时也需要使用合理的方式来保障机密计算抽象中 TCB 的安20022002年年20152015年年20162016年年20192019年年20202020年年20212021年年ARM提出TrustZoneTrustZoneIntel发布SGXv1SGXv1硬件硬件AMD发布SEVSEV硬件硬件AWS发布Nitro HypervisorNitro HypervisorAMD发布SEVSEV-SNPSNP规范Intel发布TDXTDX规范ARM发布CCACCA规范Intel发布Scalable SGXScalable SGX硬件RISC-VKeystoneKeystone开源RISC-VPenglaiPenglai开源全性与可信性，如软硬件协同安全加固、形式化验证、安全性更高的语言（例如 Rust）等。5 openEuler 和 OpenHarmony的实践5.1 openEuler 的实践2019年12月，华为创建欧拉开源项目（openEuler），通过开源的方式，把多年来积累的操作系统能力开放出来，携手产业伙伴共同发展操作系统产业；2021 年 11 月，在操作系统产业峰会上，华为携手社区伙伴，将欧拉正式捐赠给开放原子开源基金会，实现了欧拉开源操作系统从企业主导到产业主导的重要转变 28。从产业应用角度看，openEuler 打造了一套灵活的架构支持服务器、云计算、边缘计算、嵌入式等ICT和OT场景，成为面向数字基础设施统一的开源操作系统；同时，从硬件角度看，openEuler 支持多样性算力的协同释放，打造了面向 SCM 等新存储介质的存储软件栈，同时还打造了自动化、智能化的性能调优引擎。在 各 参 与 方 的 携 手 努 力 下，截 至 2022 年 3 月，openEuler 及其发行版已经实现了在十多个行业的应用，实现对 5000 多种软件的认证支持，并已兼容 60 多种整机和 200 多种主流板卡，支持鲲鹏、x86、飞腾、龙芯、申威、RISC-V 等多种处理器架构 29。5.2 OpenHarmony 的实践华为于 2020 年起陆续将其智能终端操作系统（即“鸿蒙操作系统”）的基础能力捐献给开放原子开源基金会，由开放原子开源基金会整合其他参与者的贡献，形 成 OpenHarmony 开 源 项 目，同 时 华 为 持 续 参 与OpenHarmony 开源项目的共建。09|华为研究2022 年 12 月基础软件OpenHarmony 是面向万物互联时代的智能终端统一的操作系统，为不同设备的智能化、互联与协同提供了统一的语言，为消费者带来简捷、流畅、连续、安全可靠的全场景交互体验。具有三个独有特征：一套操作系统可以满足大小设备需求，实现统一 OS弹性部署；OpenHarmony 通过组件化和弹性化等设计方法，做到硬件资源的可大可小（支持从百 KB 级到 GB 级的内存大小），并覆盖了 ARM、RISC-V和 x86 等多种处理器架构。搭载该系统的设备在系统层面融为一体、形成超级终端，让设备的硬件能力可以弹性扩展，实现设备之间硬件互助、资源共享；OpenHarmony 的分布式能力使得终端设备间能够快速发现与互联，并实现高效数据传输，以及跨设备任务协同。OpenHarmony 提供了跨终端的应用开发框架和 API一致性，面向开发者，实现一次开发、多端部署。OpenHarmony 在技术架构上整体遵从分层设计，从下向上依次为：内核层、系统服务层、框架层和应用层。系统功能按照“系统 子系统 组件”逐级展开，在多设备部署场景下，支持根据实际需求裁剪某些非必要的组件。5.3 openEuler 与 OpenHarmony 的协同创新openEuler 侧重面向数字基础设施，OpenHarmony则 侧 重 智 能 终 端。而 面 向 未 来，openEuler 和OpenHarmony 协同创新，预期将有机会打造出一个覆盖云、管、边、端能力的协同操作系统。可编程内核框架可编程内核框架多模驱动框架多模驱动框架多域融合技术多域融合技术端云协同总线端云协同总线分布式数据框架分布式数据框架分布式调度框架分布式调度框架鸿蒙系鸿蒙系统服务统服务欧拉系欧拉系统服务统服务鸿蒙基础服务鸿蒙基础服务欧拉基础软件欧拉基础软件端云协同运行时端云协同运行时鸿蒙应用框架鸿蒙应用框架欧拉应用框架欧拉应用框架鸿蒙应用鸿蒙应用鸿蒙应用欧拉应用欧拉应用欧拉应用鸿蒙/欧拉互通应用 openEuler 和 OpenHarmony 之间的能力共享：包括（但不仅限于）内核、驱动框架、协作总线、端云协同运行时环境等（见图 13）。openEuler 和 OpenHarmony 组合实现一机多域、优势互补：在一些复杂场景下例如，办公 PC 既要打造流畅、低功耗的用户体验，又要利用现有的生产力工具和应用生态可以通过打通 openEuler和 OpenHarmony，实 现“一 机 多 域”混 合 部 署（见图 14）。openEuler 和 OpenHarmony 协同突破云网边端的跨域融合：基于近远场融合软总线等技术，实现近远场设备的自发现、自连接、弹性规模和服务水平 协 议（Service Level Agreement，SLA），打造体验感知的链路管理，并实现云网边端算力互助（见图 15）。图 13 openEuler 和 OpenHarmony 能力共享图 14 openEuler 和 OpenHarmony 多域组合鸿蒙鸿蒙办公办公PCPC欧拉欧拉流畅/低功耗用户体验利用生产力工具和应用生态容器华为研究|102022 年 12 月图 15 openEuler 和 OpenHarmony 云网边端跨域融合终端设备终端设备云云&边边鸿蒙鸿蒙欧拉欧拉链路管理与算链路管理与算力互助力互助6 结语操作系统承上启下，向上服务应用，向下管理、挖潜硬件能力。本文分别从产业应用场景演进和硬件演进两个视角来观察和思考操作系统的发展轨迹。从产业应用演进看，万物智联时代产品形态多样化，要求操作系统具备弹性架构；函数计算、边缘计算等新计算形态兴起，呼唤操作系统诞生新的极致轻量、短生命周期、安全隔离的计算抽象；而系统的复杂性和敏捷性之间的矛盾，又将推动“学习型系统”的发展。从硬件演进看，异构众核 SoC、DSA 架构下的 XPU协同、以及新计算架构演进，呼唤操作系统领域研究新的计算范式；新存储介质和互联技术呼唤研究新的数据管理范式；同时，ARM V9 发布的 CCA 架构正在推动操作系统信任范式从终端设备的“信任设备、不信任应用”到云计算场景的“客户信任自己的应用，但不必信任基础设施提供商”转变，催生机密计算操作系统。openEuler 侧重面向数字基础设施，OpenHarmony则侧重智能终端，而 openEuler 和 OpenHarmony 协同创新，正在逐步打造一个覆盖云、管、边、端能力的协同操作系统体系。参考文献1 张效祥等.计算机科学技术百科全书（第三版）.清华大学出版社，2018.2 https:/en.wikipedia.org/wiki/GM-NAA_I/O3 Frederick P.Brooks Jr.,The IBM operating system/360,Software Pioneers,Springer,Berlin,Heidelberg,2002,170-178.4 Frederick P.Brooks Jr.,The Mythical Man-Month:Essays on Software Engineering,Pearson Education,1995.5 V.A.Vyssotsky,F.J.Corbat,and R.M.Graham,Structure of the Multics supervisor,Proceedings of the November 30-December 1,1965,Fall Joint Computer Conference,part I,1965.6 Dennis M.Ritchie,The evolution of the Unix time-sharing system,Symposium on Language Design and Programming Methodology,Springer,Berlin,Heidelberg,1979.7 David C.Sastry and Mettin Demirci,The QNX operating system,Computer,28.11(1995):75-77.8 https:/王怀民.分布计算 2.0：基于网络的联接计算.2020 CCF 中国软件大会特邀报告，2020.10 Mohammad Shahrad,Jonathan Balkind,and David Wentzlaff,Architectural implications of function-as-a-service computing,Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture,2019.11 Yiying Zhang and Yutong Huang,Learned operating systems,ACM SIGOPS Operating Systems Review,53.1(2019):40-45.12 Chuzhe Tang et al.,XIndex:A scalable learned index for multicore data storage,Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming,2020.13 Xingda Wei,Rong Chen,and Haibo Chen,Fast RDMA-based ordered key-value store using remote learned cache,14th USENIX Symposium on Operating Systems Design and Implementation,Banff,Alberta,Canada,November 2020.11|华为研究2022 年 12 月基础软件14 Jiachen Wang,Ding Ding,Huan Wang,Conrad Christensen,Zhaoguo Wang,Haibo Chen,and Jinyang Li,Polyjuice:High-performance transactions via learned concurrency control,in Proceedings of the 15th USENIX Symposium on Operating Systems Design and Implementation,July 2021.15 Rafael Lourenco de Lima Chehab et al.,CLoF:A compositional lock framework for multi-level NUMA systems,Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles,2021.16 Jonas Oberhauser et al.,VSync:push-button verification and optimization for synchronization primitives on weak memory models,Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems,2021.17 Tsugio Makimoto,Implications of Makimotos Wave,Computer,46.12(2013):32-37.18 Tan Kun et al.,UB:Unified and scalable memory-semantic interconnection for next-generation computing systems,Communications of HUAWEI RESEARCH,vol.1.19 Mingkai Dong and Haibo Chen,Soft updates made simple and fast on non-volatile memory,2017 USENIX Annual Technical Conference(USENIX ATC 17),2017.20 Jifei Yi et al.,HTMFS:Strong consistency comes for free with hardware transactional memory in persistent memory file systems,Proceedings of the 20th USENIX Conference on File and Storage Technologies,2022.21 Fahmida Y.Rashid,The rise of confidential computing:Big tech companies are adopting a new security model to protect data while its in use-news,IEEE Spectrum,57.6(2020):8-9.22 Sandro Pinto and Nuno Santos,Demystifying Arm TrustZone:A comprehensive survey,ACM Computing Surveys(CSUR),51.6(2019):1-36.23 https:/0680&postId=030251307616991036324 https:/www.op-tee.org/25 https:/Dominic P.Mulligan et al.,Confidential computinga brave new world,2021 IEEE International Symposium on Secure and Private Execution Environment Design(SEED),2021.27 https:/https:/openeuler.org/29 https:/www.openeuler.org/zh/compatibility/华为研究|122022 年 12 月华为 GaussDB 是由 2012 实验室中央软件院高斯部开发的企业级分布式数据库内核。该内核历经十数年的开发，现在已经被广泛应用于国内各地的企业客户，包括一些大规模金融机构。中国前七大银行中有五家选择了 GaussDB，并广泛应用在其核心业务场景如核心银行、互联网金融服务、渠道业务、客户关系管理（Customer Relationship Management，CRM）/企业资源计划（Enterprise Resource Planning，ERP）等。截止到 2021 年年底，GaussDB在中国有1500多家企业客户。本文介绍了GaussDB的架构和它的一些主打特性。GaussDB在高可用、高性能、混合负载、安全以及自治五大方面构筑竞争力。关键词分布式数据库，云化，高性能，高可用，混合负载，安全，自治，openGauss，GaussDB摘要Andy Li，任阳高斯部GaussDB：云原生分布式数据库13|华为研究2022 年 12 月基础软件1 引言图 1 GaussDB 高级逻辑系统架构2 架构随着新业务和新基础设施的出现，应用对数据库提出了新的技术要求。随着移动互联网的普及，2C 服务大量出现。金融服务、移动设备上的电子商务应用、社交应用以及物联网（Internet of Things，IoT）设备正在产生各种类型的海量数据。这一切的变化，要求改变传统业务基于柜台和集中处理的服务模式。在此背景下，数据库技术从集中式数据库走向分布式数据库，再发展到基于云的分布式数据库。为更好地满足金融、企业服务以及相关新型应用需求并高效利用云计算基础设施，华为发布了自主研发的企业级云分布式数据库 GaussDB。与传统的分布式应用架构和分布式中间件架构数据库不同，GaussDB 分布式数据库从一开始就为分布式而设计，拥有结构化查询语言（Structured Query Language，SQL）引擎、执行引擎和存储引擎等组件。GaussDB 在以下五个方面构筑自己的竞争力：高可用、高性能、混合工作负载、安全和自治。GaussDB采用基于 shared-nothing 大规模并行处理（Massively Parallel Processing，MPP）架构，支持美国国家标准学会（American National Standards Institute，ANSI）SQL 2008 标准。本文的其余部分组织如下。第 2 节介绍了 GaussDB的架构概况以及竞争力的五个主要方向。第 3 节中我们进行总结并对未来可能的工作进行了一些讨论。在这一节中，我们首先介绍 GaussDB 的架构。GaussDB 基于 shared-nothing 架构，单套数据库可以线性扩展到数百台物理机，可以并行处理各种工作负载。数据库的数据按照一定条件分布在并存储在各个数据节点（Data Node，DN）中。这些节点满足本地“原子性，一致性，隔离性和持久性”（Atomicity,Consistency,Isolation,Durability，ACID）属性，系统通过使用两阶段提交（Two Phase Commit，2PC）和全局事务管理器（Global Transaction Manager，GTM）来保证跨节点的一致性。GaussDB 同时支持行存储及列存储格式。基于列存储格式，GaussDB 实现了向量执行引擎以高效利用处理器最新的单指令多数据（Single Instruction Multiple Data，SIMD）指令，从而实现指令级别的细粒度并行。系统生成的执行计划以及执行器都针对分布式系统进行设计，可在数百台服务器上对执行计划进行并行处理，节点间按需交换数据且并行执行查询。GaussDB 采用基于时间戳的 GTM-Lite 技术，最大限度降低跨节点事务的性能衰减。系统中相关的逻辑实例有运维管理器（Operation Manager，OM）、集 群 管 理 器（Cluster Manager，CM）、GTM、协调节点（Coordinator Node，CN）和DN。应用程序通过 CN 发送 SQL 语句，经 CN 产生执行计划，下推到相关 DN 执行查询，DN 将结果汇总到 CN 上，最后由 CN 返回给应用程序。表 1 系统实例描述实例功能CN接收 SQL 语句并产生执行计划，协调DN 节点完成执行计划DN存储实际数据。DN 相互配合一起完成SQL 查询。GTM产生全局时间戳并提供全局快照。CM由 CM Agent 以及 CM Server 组成，负责集群仲裁和提供高可用能力。Gauss Data Source(GDS)提供数据并行加载能力。华为研究|142022 年 12 月2.2 高可用图 2 GaussDB 高可用能力全景图GaussDB 的高性能建立在充分利用硬件资源基础上。针对鲲鹏处理器，GaussDB 重构了数据库内核中的关键数据结构从而避免了全局共享数据结构的跨片访问，大大减少了 CPU 伪共享（False Sharing）的问题。同时GaussDB 使用鲲鹏处理器的原子“取有效地址”（Load Effective Address，LEA）指令重构了数据库中的自旋锁（Spin Lock），将自旋锁的性能提高了 4 倍。基于存储级内存（Storage Class Memory，SCM）和远程直接数据存取（Remote Direct Memory Access，RDMA）技术，GaussDB 团队研究了以内存为中心的架构和下一代分布式数据库通信网络。所有这些使 GaussDB 在单节点2-socket 鲲鹏服务器上提供 150 万 tpmC 处理能力，在单节点 4-socket 鲲鹏服务器上提供超过 230 万 tpmC 处理，线性伸缩比达到 1.5。此外，GaussDB 通过以下四个方面增强系统性能。Shared-Nothing 架构，GaussDB 将数据按照一定规则分布在各个 DN 上。在执行查询时，DN 在本地处理自己的数据，并根据需要在节点之间打散数据。对称多处理（Symmetric Multiprocessing，SMP）技术，为了充分利用现代 CPU 多核能力，GaussDB实现了查询的 SMP 技术。在一个节点内，数据被分成多个部分并由不同的线程并行处理。在一些计算密集型的查询中，系统可以充分利用CPU来加速查询处理。指令级并行（Instruction-Level Parallelism，ILP）技术，基于现代 CPU 的 SIMD 能力，GaussDB 实现了向量执行引擎。向量执行引擎以批处理模式（每次 1000 个 tuple）处理数据，使得系统在 TPC-H 和TPC-DS 基准测试中获得高分。2.1 高性能 动态编译技术，为了不断提高处理性能，我们采用了动态编译策略。使用低级虚拟机（Low Level Virtual Machine，LLVM）技术精简查询涉及的 CPU 指令数，从而提升查询性能。GaussDB 的高可用能力包括五个部分：防错、容错、纠错、快速定位和服务可用性。从初始设计开始，GaussDB 的架构理念是防止系统单点故障（Single Point of Failure，SPOF），系统的相关硬件交换机、网卡和电源等硬件组件通过冗余达到该目标。对于本地盘，系统使用 RAID5 阵列提供数据保护，防止单个磁盘数据损坏时导致业务中断，对于 EVS 云盘，系统使用云盘自身的多副本机制提供数据可用性。除了硬件冗余外，系统对于实例角色的架构设计也采用高可用架构，系统中 CN 采用多副本对等架构、DN 采用主备副本机制，CM、GTM 等也都采用温备份机制。各个角色的主备裁决均由 CM 进行，CM 自身的主备裁决依赖于分布式键值存储系统（Editable Text Configuration Daemon，ETCD）组件。CM 作为集群的大脑，决定实例的主备角色。其自身有多个温备份，当系统主 CM 的主实例发生故障时，经过 ETCD 裁决，选择一个 CM 备进行升主操作，从而接管集群仲裁能力。GTM 和DN 等角色的主实例和温备实例定期向 CM 主实例发送心跳。根据心跳，CM 确定各个角色的主实例，并在主实例故障时进行切换。除此之外，GaussDB 提供多种日志分析工具、核心转储分析工具、分布式跟踪工具等，在系统出现故障时提供高效问题定位手段。同时，GaussDB 还提供运维操作不中断服务的能力，在线升级和在线扩容功能可以保证在升级和扩容操作时业务工作流程不中断。15|华为研究2022 年 12 月基础软件2.3 混合工作负载2.4 安全能力在实际金融行业的生产系统中，根据不同业务的高可用要求，GaussDB 提供多层次的高可用能力：单个可用分区（Availability Zone，AZ）高可用、跨 AZ 高可用以及跨 Region 高可用能力。在 AZ 中，基于无单点故障的设计，GaussDB 在提供 RPO=0，RTO 10s 的高可用能力。在保证 AZ 级高可用能力基础上，GaussDB 在 100 物理节点上能够提供 1.2 亿 tpmC 的超高性能。GaussDB提供跨 AZ 集群部署，提供强一致性以及对应的高可用能力（RPO=0 和 RTO 1，（值最大化）秘书问题都有一个确定性算法，算法的期望竞争比渐近为gc,()，表示为：函数f(c)是依据 Lambert W函数的两个分支W0和W1得出，写作f(c)=expW0(1/(ce)expW1(1/(ce)。在线二分匹配。在线二分匹配问题中，有二分图G=(L R,E)（其中，|L|=n且|R|=m），其节点集L以均匀随机顺序在线到达 73,66。一个节点到达后，会显示与各邻居之间的边权重R。算法必须不可撤销地决定是否把到达的在线节点匹配给R中的某个（当前尚未匹配的）邻居。针对此设定，Kesselheim 等人 66 给出了一个紧的1/e-竞争确定性算法，对经典秘书算法中的相同保证进行了显著泛化 77,37。此设定中的预测结果即为值向量p=(p1,.,pm)，在某个固定最优（离线）二分匹配中，该向量可以预测节点r R相邻各边的权重。也就是说，预测值p表示存在一个固定的最优二分匹配，该匹配中的每个节点r R都与一条权重为pr的边相邻。于是，预测误差就是取r R所有节点的最大预测误差，并在所有最优匹配中最小化。这样就实现了经典秘书问题中预测能力的泛化。这种类型的预测与顶点加权在线二分匹配问题高度对应 2。4 的研究显示，对于任意 0和c d 1，在线二分匹配问题存在一种确定性算法，算法的期望竞争比渐近为gc,d,()，表示为：式中，|为实例中最优（离线）匹配的基数。装箱。装箱是经典的优化问题，也是一个 NP 难问题。在装箱问题的在线变种版本中，事先并不清楚物品集，物品是以序列的形式逐一呈现。一个新物品到达时，在线算法将其放入一个已打开的现有箱子中（以不超出箱子容量为前提），或放入一个新的箱子。假设每个物品的大小是1,k中的一个整数，k表示箱子的容量这也是 27,41,110 等许多有效装箱算法所依赖的自然假设。此外，在不限制物品大小的前提下，88 的研究发现，如果在线算法输出的大小建议与输入的大小呈次线性关系，那么算法的竞争比不优于1.17（即使该建议为零误差）。这一负面结果意味着，为了利用基于频率的预测，需要对物品大小进行限制。考虑输入序列。对于任意x 1,k，令nx,表示中大小为x的物品数量。定义fx,，表示中大小x的出现频率，令该频率等于nx,/n，于是有fx,0,1。算法使用这些频率作为预测值。具体而言，对于每个大小x（x 1,k）在中的出现频率，都有一个预测值，表示为fx,。预测会有误差，所以通常情况下，fx,?=fx,。为量化预测误差，令f和f分别表示中大小x的出现频率及其预测值，也即 k 维空间中的点。根据前文有关预测式在线算法的研究（如 104），误差即为f与f之间距离的 L1 范数。gc,()=max1ce,f(c)(max1 opt,0)if 0 gc,()=1ceif gc,d,()=max1cln(cd),d12c(max1( )|opt,0)if 0 1cln(cd)if 华为研究|642022 年 12 月度量任务系统。给定包含一系列状态的度量空间M，其中的状态可以解释为动作、投资策略或者某种生产机器的配置。算法从预定义的初始状态x0开始。在每个时间点t=1,2,.，有成本函数t:M R 0, ，算法的任务是决定要停留在状态xt1并支付成本t(xt1)，还是要移动到（可能成本更低的）另一状态xt并支付成本dist(xt1,xt) t(xt)，其中dist(xt1,xt)表示在xt1和xt两个状态间迁移的成本。算法的目标是最小化随时间推移所产生的总成本。在每个时间点t，预测器都会针对算法在该时间点应处的状态生成预测值pt。对于某个离线算法 OFF，预测误差为：式中，ot表示 OFF 在时间点t所处的状态，T表示输入序列的长度。3 证明了两种一般化的结果。其一，令A为-竞争的确定性在线算法，用于求解度量任务系统（Metrical Task System，MTS）问题P。存在一种求解问题P的预测式确定性算法，与任意离线算法 OFF 相比，该算法实现了9 min,1 4/OFF的竞争比，其中表示相对于OFF的预测误差。其二，令A为-竞争的随机在线算法，用于求解 MTS 问题P，问题的度量空间直径为D。对于任意 1/4，存在一种求解问题P的预测式随机算法，实现低 于(1 )min,1 4/OFF OFF O(D/)的 成本，其中表示相对于 OFF 的预测误差。于是，若 OFF（近似）最优，且 OFF，则竞争比接近1 。=T?t=1t;t=dist(pt,ot)13.1.2 预测式流算法数据流模型是一种基础模型，用于在内存有限的情况下快速处理海量数据集。60 研究了一种大流量对象神谕，能够预测某个数据元的出现频率是否高于给定阈值。研究表明，这种神谕可以应用于数据流中的广泛问题。借助该神谕，研究人员获得了此类问题的第一个最优界限，有时界限还突破了未使用该神谕时的已知下界。研究中还将该神谕用于流差异中离散元数量的计算、频率矩的估计、级联聚合的估计，以及几何数据流的矩估计。针对离散元问题，该技术能够突破已知下界，从而得到一种新的空间最优算法。对于0 p 2时第p个频率矩的估计，则实现了二次方量级的内存节省，突破了无神谕时的已知下界。设数据流模型中有基础频率向量x Zn，初始化为0n，该值随着流的过程而演变。该流由形如(i,w)的更新组 成，即xi xi w。设 流 的 过 程 中 有M，且 令|x|=maxi1,.,n|xi|M。在流的结尾处，要求为函数f:Zn R近似出函数f(x)。由于流的规模很大，多数算法采用近似和随机的处理方式。通常做法是，算法输出一个估计值Z，值的范围为P(1)f(x)Z(1 )f(x)2/3，式中的概率取决于算法使用的随机种子，而与输入流的随机性无关，即输入流可能为最坏情况。以恒定次数独立重复运行算法，并获取中位数估计，可以将成功概率2/3替换为大于1/2的任意常数。算法的空间复杂度以比特为单位，目标在于减少存储x所需的空间，使得实际所用空间显著少于平凡n比特空间。考虑在数据流模型下对以下公共函数f(x)进行估计。离散元：f(x)=|x|0，式中|x|0为x的非零坐标数量，定义为|x|0=|i:xi=0|。此数量用于拒绝服务（Denial of Service，DoS）攻击的检测和数据库查询的优化 61。Fp矩：f(x)=|x|pp，式 中x的p范 数 定 义 为|x|p=(?i|xi|p)1/p。当0 p 2时，这些范数用于估计斜率和峰度 58。(k,p)级联范数：该问题中，x是一个n d矩阵，可以 接 收 对 其 单 个 条 目 的 更 新，且 有f(x)=|x|k,p:=(?i(?j|xij|p)k/p)1/k。该 矩 阵 有助于对数据库执行多个查询 26,59。假设有一个大流量对象神谕，基于输入i n，判断流结尾处的xi是不是大流量对象，并输出判断的结果。大流量对象的定义因数据流问题的类型而异。神谕则分两类，第一类指示|xi|T是否成立，第二类指示|xi|p1T|x|pp是否成立，其中T表示与问题关联的预设阈值。我们将使用第一类神谕来处理离散元问题，而使用第二类神谕来处理所有其他问题。在x的坐标存在增删的情况下，要估计L0=|x|0，目前的最佳算法由 61 提出。61 的研究表明，基于训练好的神谕，有一种算法可以得到(1)-近似的L0，算法使用的空间为O(2(logn)log(1/)，成功概率至少为2/3，更新与上报时间为O(1)。61 还得出以下结果。在大流量对象神谕的完美假设下，可以在1 2因数内估计|x|pp，空间复杂度为O(4n1/21/plog(n)log(M)比特，成功概率至少为3/5。考虑神谕给出错误预测的概率为 0。那么，在1 2因数内估计|x|pp时所需的空间，当=O(1/n)时 为O(4(n)1/21/plog(n)log(M)比特，否则为O(4(n)12/plog(n)log(M)比特。这两种保证都具有至少3/5的成功概率。65|华为研究2022 年 12 月软件理论令0 p 2且0 1s|x|pp）。假设大流量对象神谕出错的概率为=O?2log2(1/)log log(1/)?，那么也存在具有相同保证度的算法。对于级联范数，设 0和k p 2为常数。存在一种随机算法，以坐标增删流的n d矩阵x为输入，可以按至少2/3的概率将(1 )-近似的结果输出到|x|k,p，使用的空间为O(n11kp2kd121p)。此外，在大流量对象神谕的假设下，存在一个矩形高效的单通流算法，当p 2时，以1 的概率将(1)-近似的结果输出到|x|pp。处理流中的每个矩形时，使用的空间为O(d(1/21/p)比特，时间为O(d(1/21/p)。3.2 学习后优化3.2.1 基于样本的优化本节回顾“学习后优化（Learning to Optimize）”的当前研究进展，考察了“基于样本的优化”和“面向噪声的优化”两个主要研究方向。以下介绍这两个方向涉及的数学模型，以及不同设定下的不可能结果和算法结果。本节将历史数据看作从某个基础分布中提取的样本，目的是研究如何基于样本数据来优化目标函数。考虑以下形式的（约束）组合优化问题：maxSMf(S)式中，f:2N R为目标函数，M 2N为约束集合。假设存在值神谕Of，可以返回子集S N的值f(S)。为评估用于优化的样本的能力，Balkanski 等人 11 首次提出以下模型，称之为基于样本的优化（Optimization from Samples，OPS）。定义 3.1：OPS 模型给定函数f:2N R，设S:=Si,f(Si)ti=1为样本的集合，其中每个Si都是从某个基础分布D中抽取的独立同分布样本。给定参数(0,1，若要使函数族F:2N R对于分布D和约束M是-可近似的，则需存在算法A，在给定误差参数(0,1)并以集合S为输入的情况下，输出结果S M并满足：PrS1,.StDt?EAf(S)maxTMf(T)?1 1式中，被称为近似比，t表示样本复杂度。还需注意，此处并不要求A为多项式算法，因为我们关注的是 OPS 模型下样本的功效。显然，分布D显著影响F的可近似性。譬如，若D总是返回空集或固定的子集，则无法期望从样本中学习到足够的信息用于优化。因此，要考虑分布的“合理性”，并考察在查询模型Of下可近似的函数到了 OPS 模型下是否仍然可近似，比如次模函数。为此，Balcan 等人 8 提出的 一 个 名 为 PMAC-可学 习 性（Probably Mostly Approximately Correct Learnability）的函数族进入了人们的视野。大体来说，若对于任意子集S D，可以通过样本集合S高概率地学习到f(S)，则说函数f对于某个分布D是 PMAC-可学习的。PMAC 包含大量的函数族，其中，OPS 模型下研究得最多的是覆盖函数和影响函数。下面先介绍覆盖函数的定义。定义 3.2：覆盖最大化给定二分图G=(L,R,E)，L和R分别表示左、右节点集，E表示L和R之间的边集。覆盖函数f:2L R0被定义为子集S L的邻居数量，即f(S)=|N(S)|。覆盖最大化问题在于选择一个大小为k 1的子集S L，使得f(S)最大化，即maxSL:|S|=kf(S)。值得注意的是，覆盖最大化问题是 PMAC-可学习的 6，在查询模型下可采用(1 1/e)-近似贪心算法求解98。接下来介绍影响函数的定义。可以认为，影响函数是覆盖函数泛化后的一般有向图，它在社交网络中应用甚广。定义3.3：影响最大化给定有向图G=(V,E,p)，V为节点集，E为边集，pe为E中每条边e E的概率向量，每个节点有已激活或未激活两种状态。给定种子集S0，令其在时间点t=0处于已激活状态，接着按下述过程激活其他节点：首先，在时 间 点t=1,2,.，令St=St1。然 后，对 于 任 意v/St1，令Nin(v)表示节点集合u，且有(u,v)E。每个节点u Nin(v)(St1 St2)以概率puv独立地激活v，最后将所有已激活节点v添加到St。当不再有新的节点 被 激 活 时，就 得 到 一 个 已 激 活 子 集 的 序 列S0 S1 S2。给定S0，定义(S0)为最终已激活节点 的 集 合，并 将 影 响 函 数f:2V R定 义 为f(S)=E|(S)|即种子集S0的期望已激活数量。影响最大化问题在于选择一个大小至多为k的种子集S，使f(S)最大化。华为研究|662022 年 12 月需要注意，覆盖函数和影响函数都属于次模函数。1OPS 模型可以自然地分成两个步骤：1.基于具备 PMAC-可学习性保证的样本，构造函数f，作为对f的估计。2.在查询模型f下优化原有问题。不过，接下来我们会看到，虽然这两个步骤都不难实现，但一旦组合起来可能就无法得到合理的（近似）算法。下面介绍目前在 OPS 模型下的不可能结果和算法结果，模型包含覆盖最大化和影响最大化这两个问题。不可能结果。Balkanski 等人 11 首先研究了 OPS模型下的覆盖最大化问题，提出以下定理。定理 3.4：覆盖最大化问题的不可能结果 11对于任意分布D，覆盖最大化算法的近似度不优于n1/4的紧界限，无法实现所观察样本数少于指数数量的目标。这一结果有些出乎意料，因为覆盖最大化问题已被证明是 PMAC-可学习的 6。得出该结果的主要思路是构造一类函数，使这些函数从分布D的多数子集学习时可以获得较好的学习效果，但不足以学习到（近似）最优解，如此一来，样本就无法提供足够的信息用于优化。不可能结果也存在于其他问题设定中。Balkanski 等人 12 构造了一类次模最小化问题f:2N 0,1，并证明任何基于多项式样本的算法都无法提供(1/2 O(1)加性近似。此结果可以扩展到凸最小化领域 13。总体而言，我们注意到，即使函数是 PMAC-可学习的，在查询模型和 OPS 模型下的可近似性仍可能存在巨大的差别。为克服上述不可能结果，进一步研究的进展如下。算法结果。一般可以通过三种尝试来获得算法结果。第一种是假设f满足额外属性。例如，Balkanski 等人 10考察了曲率为c 0,1的单调次模函数。2通过研究，他们提供了一个紧的(1 c)/(1 c c2)-近似算法。该算法符合我们对 OPS 模型下线性函数可求解的直觉。不过，覆盖函数和影响函数的曲率都是1。对于影响最大化问题，Balkanski 等人 9 假设社交网络G由随机块模型生成，并提出一种常数近似算法。总体而言，这种尝试并没有改变 OPS 模型，因此，需要为不同的优化问题设计特定的属性。第二种尝试是弱化 OPS 模型的目标。Rosenfeld 等人 107 并未对整个函数进行优化，而是提出了一个基于样本的分布性优化（Distributional Optimization from Samples，DOPS）模型。模型的目标是，对于从同一分布中抽取的一个较小样本集合和另一个未知的较大样本集合，可以基于这个较小集合，从较大集合中找到优化的样本。该 研 究 证 明，在 DOPS 模 型 下，可 近 似 性 与 PMAC-可学习性是等价的。这种尝试为采样模型下的 PMAC-可学习性提供了解释。然而，我们可能仍希望对合理分布D找到全局最优解。第三种尝试则假设我们不仅拥有样本Si的值f(Si)，还获得了额外的结构化信息。Chen 等人 23 首先针对覆盖最大化问题，对这一方法开展了研究，提出以下基于结构 化 样 本 的 优 化（Optimization from Structured Samples，OPSS）模 型。模 型 中，每 个 样 本 由(Si,NG(Si)表示，NG(Si)为Si的邻居集合。该研究证明，如果D满足某项温和的假设（比如D是某种均匀分布），那么可以为覆盖最大化问题求得O(1)-近似的解。此外，Chen 等人 24 还将这一结果扩展到影响最大化问题，问题中的各样本表示为(Si,0,Si,1,.,Si,n1)，形式上由完整的传递路径组成。基于D是乘积分布的假设，该研究提供了一个常数近似算法。总结而言，额外的结构化信息可以弥补可学习性和可近似性之间的差距。另外，结构化信息因问题而异，因此考察适用于其他问题的结构化信息将有所裨益。3.2.2 面向噪声的优化2曲率用于测量次模函数趋于线性的程度。曲率越接近 0，次模函数就越趋于线性。1 若对于任意S T N和u/T，有f(S u)f(S)f(T u)f(T)，则认为f是次模函数。如前文所述，OPS 模型下的主要困难似乎在于，可能无法基于样本估计来得到最优解的值。那么进一步的问题是，如果能对所有子集进行估计，是否就可以实现优化呢？这 就 引 出 另 一 研 究 方 向“面 向 噪 声 的 优 化（Optimization with Noises）”，也即可以学习到函数f，作为基础目标f的估计，使得对于任意S 2N，有f(S)(1)f(S)。此处，(0,1)表示噪声参数，值越小越好。要获得f这个估计值，可以基于历史样本，通过神经网络或构建草图的方式来学习。出乎意料的是，即使得到了f，优化问题仍可能很难求解。下面讨论误差神谕（Erroneous Oracle）和噪声神谕（Noisy Oracle）两种设定下的情况。误差神谕。Hassidim 等人 48 提出一个误差神谕，对任意S 2N，有：f(S)=S f(S)式中，S 1,1 。此处，S可以由对手选择。该研究证明了以下定理，表明使用误差神谕很难求解次模最大化问题。67|华为研究2022 年 12 月软件理论定理 3.5：使用误差神谕时的不可能结果 48有误差为的神谕。存在基数约束，使得对误差神谕的查询少于指数次。在此约束下，要使单调次模函数最大化，任何随机算法都无法达到n0.5 的近似度。该研究的主要思路是构造函数f1和f2，两个函数对于几 乎 所 有 子 集S 2N都 互 相 近 似，比 如f1(S)(1)f2(S)。因此，对手可以选择噪声参数S，使得对于这些子集无法将f1和f2区分开来。然而，f1和f2的最优解值存在很大差异。Hassidim 等人 48 证明，在此设定中，多项式查询数量不足以区分f1和f2。为消除这种不可能的结果，Hassidim 等人 48 提出一种噪声神谕，它的S D是从独立同分布中抽取的样本，而非由对手选择。该研究利用噪声神谕，获得了(1 1/e)的近似度。但是，算法所要求的查询数量必须达到nO(1/)，复杂度仍有待降低。本节从“学习后优化”的两个方向“基于样本的优化”和“面向噪声的优化”，回顾了相关研究进展。这些研究颇具启发性，但仍然存在若干问题有待解决，譬如，需要有更合理的模型以消除不可能结果，现有算法结果的样本复杂度或查询复杂度也有待降低。4 启发式算法与机器学习的组合4.1 控制策略的学习接下来，我们介绍启发式算法与机器学习的组合。与理论算法相比，在启发式算法中运用机器学习时，可以认为启发式算法是负责高阶结构的控制，同时调用机器学习模型来辅助低阶决策。图 3 总结了这一学习增强框架。算法通常为解决某类一般性问题而设计，换句话说，可以从这类问题中获取任意可求解的实例作为输入，进而输出所需的解。而且，理论研究通常基于所有问题实例的最坏情况来分析算法的属性，如收敛速度和近似比。然而，对于实践中的每个特定实例，算法的性能通常对算法参数和初始解的选择非常敏感（如果没有预先指定算法的初始解）。因此，很自然的思路是，通过学习为算法找到针对具体实例的最佳控制策略，而无需改造算法本身。本节将这种方法命名为“学习增强算法（Learning Augmented Algorithm）”，并回顾相关研究进展。我们先介绍两个具有代表性的研究方向“控制策略的学习”和“热启动的学习”，再探讨被称为“适应性学习增强”的新兴方向。图 3 组合优化算法会重复查询同一机器学习模型以做出决策。机器学习模型以算法的当前状态为输入，算法可包含问题定义。算法的控制策略主要指超参数，例如迭代算法的更新率，或启发式算法的搜索策略。本节介绍分支限界算法的一个应用示例，并总结与控制策略学习相关的其他类似学习增强算法。分支限界法简称 BnB（Branch and Bound），主要是指求解离散优化问题的一种范式。考虑基于可行集S来最小化实值函数f的问题，其中S是离散值。BnB 算法通常从单个根状态开始，并维护一个已激活节点的队列L，该队列容纳S的子集，同时用作目标的全局上下界。只要队列L不为空，BnB 算法就使用某种节点选择策略，每一步从L中弹出一个节点Si S，通过必要的松弛、并利用高效求解器，计算出受子集Si限制的目标界限。BnB 算法根据局部界限和全局界限来区分三种可能的情况：1.局部下界大于当前全局上界，这意味着，不可能通过进一步生成子集分支的方式来获得更好的解，因而修剪掉该子树（子集）。2.局部下界与局部上界匹配，则找到受限于子树（子集）内的最优解。3.否则，生成Si的所有分支，并将这些分支推回L。在情况 2 和 3 中，会相应更新全局上下界。当L为空或全局上下界的差距足够小时，算法终止。BnB 算法最重要的控制策略是节点选择策略，准确地说就是，如何从队列中选择下一个子集来计算界限并决定是否生成分支。通常来说，一个好的策略可以尽快找到最优解。这就是说，策略必须先选择适当的分支子集，以便尽快找到好的解，并修剪掉多数不必要的子树（子集）。有几种策略在传统的应用中很流行，包括众所周知的先进华为研究|682022 年 12 月先出和后进先出策略，以及依赖另一优先级队列的最佳优先策略按局部下界对节点排序就是其中一例。另一种直接的思路是，利用训练数据来处理待求解的问题，从而学习到一个好的策略。尽管问题和队列都有定制化的表示，但自然的学习过程仍在于学习每个队列中最可能的节点，从而找到问题实例的最优解。Bai 等人 7 应用了此范式来求解两个输入图之间的 最 大 公 共 子 图（Maximum Common Subgraph，MCS）。该研究把待分支的子集设计为输入图之间可能的节点对，利用强化学习，将所找到的公共子图最大化，从而学习到这些节点对。Liu 等人 79 也考虑了类似的方法，将学习目标设置为最小化分支生成的次数。相比于基于端到端学习的 MCS 问题求解器，这两种学习增强 BnB 算法都实现了更好的性能。He 等人 49 应用了此范式来解决 MILP 问题。待分支的子集天然就是变量以及这些变量所属的区域。除了学习每个状态的恰当分支变量，该研究还学习到一个剪枝策略，用于预测最优解是否属于某个子树（子集）。剪枝策略进一步促进算法加速，由于已经预测出不包含最优解的多数子树，因而可以忽略这些子树的局部上下界计算。与面向 MILP 问题的 SOTA 求解器相比，这两种控制策略的运用都使 BnB 算法在速度和最优间隙方面获得了更好的性能。还有一些其他的研究路径，针对 MILP 问题设计出不同的机器学习技术，学习到分支限界树上每个节点所做的分支决策 68,80,52。类似地，针对 MILP 实例，Kruber 等人 74 使用机器学习预先确定 Dantzig-Wolfe 分解的应用是否会有效。Bonami 等人 21 使用机器学习来确定对问题的线性化处理是否有助于更快地求解。机器学习还可以用于选择 MILP 求解器和启发式构建框架的攻击性参数 62,85。此外，在二次规划(Quadratic Programming，QP)领域，Baltean-Lugojan 等人 14 利用了机器学习来选择合适的切割平面。缺点。学习到的控制策略通常由神经网络表示，执行这些策略也会占用计算资源、需要时间预算。在提到的 BnB 示例中，算法每次决定一个分支节点时都会调用策略。这意味着，学习到的控制策略必须大幅提高原有算法的性能，才能覆盖额外的成本。4.2 热启动的学习然而，针对特定问题实例，热启动能够预测恰当的初始解，这种能力肯定有助于提高算法的性能。例如，如果迭代算法的初始解足够接近最优解，那么算法获得最优解所需的时间自然就更少。这正是新近一些研究工作的出发点。这些工作基本上就是针对部分问题实例，基于训练数据学习到预测模型，进而获得问题的最优解。而其他工作中的问题实例则应用传统算法，并使用热启动作为预测解。例如，Bemporad 和 Naikr 的论文 18，以及 Masti 和 Bemporad 的论文 86，都基于这一思路来学习 BnB 算法的热启动，从而求解 MILP 问题。Duan 等人 35 将预测解作为热启动，应用于求解纳什均衡的传统算法，在计算效率和近似最优性方面都取得了相似的改进效果。缺点。“热启动学习”所采用的方法，存在与“控制策略学习”共通的缺点，即在求解每个问题实例之前，都要进行额外的神经网络推理。而且，针对特定算法学习最优热启动的研究甚少。从理论上讲，尚不清楚是否初始解越接近最优解，相应的热启动就越好。相反方向的研究。一种有趣的观点是，可以反过来把“热启动的学习”看作是传统算法对机器学习的增强。例如，Li 等人 76 设计了一个学习框架来求解组合优化问题，主要涉及三个等效问题最大团（Maximum Clique，MC）、最大独立集（Maximum Independent Set，MIS）和最小顶点覆盖（Minimum Vertex Cover，MVC）。这个学习框架为每个输入实例输出一组解，并运用局部搜索算法加以改进，最终找到最优解。然而，在 MC、MIS、MVC 的传统求解器中，先使用简单的方法生成初始解，然后运用局部搜索算法，是很常见的做法。换言之，这种学习方式其实就是为局部搜索学习到一组好的热启动。4.3 适应性学习增强虽然许多启发式算法会将初始解构造为算法的第一个迭代步骤，但与控制策略相比，初始解的好坏似乎并不那么重要。类似情况也出现在许多算法的理论分析中。除专门用于识别初始解的算法以外，随机初始化或任意较差初始化算法的收敛性和最优性通常都得到了证明。前两种学习增强方案可以看作是“静态增强”，因为控制策略或热启动的学习模型在增强算法的运行过程中是固定的。最近一项工作 118 设计的学习过程则不同，它以每个问题实例为输入，在算法运行过程中进行适应性地学习增强。本节简要介绍这项工作所研究的问题、增强后的启发式算法，以及对应的学习框架。旅行商问题定义为一个完整的无向图，图中每条边都有一个成本，表示这条边的两个端点之间的距离。该问题在于找到一条哈密顿线路，使线路中各条边的成本总和最小。LKH（Lin-Kernighan-Helsgaun）算法是一种基于局部搜索的著名启发式算法，用于求解旅行商问题。LKH 算法从初始解开始搜索，迭代运行一种名为k-opt 的特殊局部搜索技术。每个k-opt过程会考虑当前解的k条边，测试这些边的2k个端点之间的一系列其他k条连接，并使用最优选择（最小总成本）来替换这k条边。LKH 算法的69|华为研究2022 年 12 月软件理论关键是根据值（及其扩展）来选择这k条边。此处忽略详细的计算，人们通常认为，具有较小值的边更有可能构成旅行商问题的最优解。Zheng 等人 118 设计了一个强化学习过程来取代 2-opt 过程。该过程基于值确定每条边的初始 Q 值。之后每一步，系统的状态为节点pi，采取的动作是根据 Q 值选择该节点的一条邻边(pi,pi 1)，而后系统迁移到下一节点pi 2，该节点连接到原有解中的pi 1（这个操作实际是将上一个解中的两条边(pi1,pi)和(pi 1,pi 2)替换为另两条边(pi,pi 1)和(pi 2,pi1)，而不影响解的可行性)。只要将每个状态动作对的奖励设置为解的改进程度，就可以通过标准强化学习来更新 Q 值。该方法结合了强化学习技术和传统启发式过程，与LKH 算法相比，在求解大型旅行商问题实例方面取得了更好的性能。Q 值作为值的增强，在这个过程中发挥了重要作用。Q 值具有适应性更新的优雅设计，这种设计一方面为学习增强提供了新的潜力，另一方面也依赖于大量有关问题结构和启发式算法本身的领域信息。5 基于学习的机制设计5.1 拍卖设计中的机器学习本节的拍卖设计问题围绕以下设定展开讨论。一个卖家，拥有一个m件物品的集合。一个n名竞拍者的集合，竞拍者具有独立私人估值vi:2m R0，其中i=1,2,.,n。每个竞拍者i的估值遵循已知分布vi Fi。一个拍卖机制，由分配规则g()和支付规则p()表示。当竞拍者i出价bi、其他竞拍者出价bi时：gi(bi,bi)表示物品分配给竞拍者i的概率（向量）；pi(bi,bi)表示竞拍者i需要支付的金额；于是，竞拍者i的收益定义为 ui(vi,bi,bi)=vTi gi(bi,bi)pi(bi,bi)。设 计 一 种 机 制，使 得 在 以 下 约 束 下，期 望 收 入Ev1F1,.,vnFn?ipi(vi,vi)达到最大化。激励相容约束：i,vi,bi,vi,ui(vi,vi,vi)ui(vi,bi,vi)个体理性约束：i,vi,vi,ui(vi,vi,vi)0Myerson 95 提供了m=1时的收入最大化拍卖机制，但即使m=2，也不存在完整的解析解结果。之后的许多工作针对多件物品的设定来设计最优拍卖，设定中假设竞拍者数量固定（通常为两个），或估值分布的支撑集是有限的（仅包含两个取值）。其他工作还研究了与最优收入具有恒定近似比的机制设计。Duetting 等人 36 首次引入深度神经网络表示拍卖机制。这种表示方式把拍卖设计问题转移到深度学习任务中，不仅近似地还原出已知的最优机制，而且在相应设定下，获得了比近似最优机制更多的期望收入。准确地说，神经网络将分配规则g()和支付规则p()参数化为g()和p()。具体表达式写作pi=i(vTi gi)，式中i 0,1，该 表 达 式 直 接 满 足 个 体 理 性 约 束。激 励 相 容 约 束 则 被 转 移 到 一 组 损 失 函 数rgti=Ev1F1,.,vnFnmaxbiui(vi,bi,vi)ui(vi,vi,vi)中，函数表示每个参与者对不谎报的后悔程度。若对所有i，有rgti=0，则满足激励相容约束。于是，训练过程会从已知 分 布 中 抽 样 竞 拍 者 估 值，合 并 负 值 期 望 收 入Ev1F1,.,vnFn?ipi(vi,vi)与rgti，并使用随机梯度下降法更新神经网络的参数。Feng 等人 38 将上述方法应用到带预算约束的设定中。Sakurai 等人 109 进一步引入防假名约束，利用类似激励相容约束的损失函数，防止竞拍者操纵虚假身份参与拍卖而从中获益。Shen 等人 112 也采用类似的思路，使用了神经网络参数化机制，但不同之处在于，该研究使机制设计可以看作算法设计的一个特殊过程，该过程认为参与者都是理性的。准确地说，可以定义一个算法，将特定问题的任意实例作为输入，进而返回满足某种预期属性的输出。而机制设计好之后，参与者为机制提供输入实例，并从机制的输出中受益。因此，在设计机制时，必须同时考虑机制的目标和参与者谎报的激励。机制设计的自然思路是给参与者设计一种博弈，使用参与者的动作作为输入，使得博弈的纳什均衡产生预期的输出。幸运的是，根据著名的显示原理，我们可以专注于真实机制的设计，真实机制会如实报告每个参与者的均衡策略。这是因为，当参与者运用均衡策略时，如果机制优化了一个目标，就会有一个等效的真实机制来采纳参与者的真实报告并模拟最优机制。不过总的来说，机制仍然很难设计，尤其在各参与者报告多项输入的场景中，这种困难体现得更为明显。传统的研究工作通常会为设计好的机制提供解析形式的实现，并从理论上证明其（近似）最优性。这在一定程度上限制了面向大规模问题的机制设计研究。有所不同的是，一个新兴的研究方向使用了深度神经网络来表示复杂的机制，显示出克服这种困难的潜力。本节将这个研究方向称为“基于学习的机制设计”，并总结了新近的相关研究。我们首先介绍最具代表性的机制设计问题拍卖设计，也称“与金钱有关的机制设计”，多数研究都与此相关。然后，在“与金钱无关的机制设计”方面，我们再介绍一些基于学习的应用。最后，我们探讨了一种拍卖设计与机器学习的新组合。华为研究|702022 年 12 月用另一个网络替代了与激励相容约束相关的损失函数，新的网络表示竞拍者在给定机制下采取的最优动作。换言之，研究中并未采用显示原理，转而从一个更大的参数化空间中搜索最优拍卖机制。Rahme 等人 105 进一步将机制网络与竞拍者网络之间的互动建模为两人博弈。另外，Cai 等人 22 对学习辅助式拍卖设计进行了动态扩展，研究了重复拍卖的情形，使得机制与竞拍者都可以随时间演进。然而，为了获得令人信服的性能，他们将拍卖机制的设计空间限制为带保留价的二价拍卖，并使用强化学习来找到每个时间周期中的最优保留价。最近，Liu 等人 78 还将基于学习的拍卖机制应用于广告拍卖的现实场景中，拍卖中假定投标人的估值分布具有特定结构。其他相关工作。前文介绍的工作主要考察了基于学习的机制设计方法。另有大量论文研究了需要多少样本才能通过理论分析学习到拍卖机制。这个问题更为基础，本文不作相关工作的评述。5.2 金钱无关机制设计中的机器学习6.1 组合优化与模式识别的比较5.3 面向学习式参与者的拍卖设计典型情况是，卖家反复拍卖同一类型的物品，而独立买家（可能具有完全相同的估值分布）使用无悔学习算法来找到合理出价，从而实现长期收益的最大化（即最大限度地降低后悔程度）。Nekipelov 等人 97 首次开展了相关研究，针对二价拍卖，基于买家都是无悔学习者的假设，考察如何估计买家的出价。最近，Deng 等人 29 又考察了一价拍卖。一价拍卖尚无纳什均衡的理论表征。该研究指出，存在一种无悔学习算法，可以让买家获得纳什均衡。6 限制与挑战上述拍卖机制是用分配规则和支付规则表示的，而很多其他的机制设计问题并不涉及支付规则。这类问题被称为与金钱无关的机制设计。由于这类机制设计不具备统一的设定，我们只介绍一项最近的工作，它研究了如何通过机器学习来增强机制设计。Golowich 等人 47 研究了设施选址问题，即政府要求参与者报告自己的位置，然后从中找到一个对所有参与者都有利的设施建造位置。该研究采取类似 38 的思路，将“选址规则”表示为神经网络，以参与者的报告为输入，进而输出设施的选址。经过训练，神经网络会最小化设施位置与每个参与者之间的总（加权）距离。每个参与者谎报的激励（谎报的目的是使设施位置尽可能靠近自己）转换为训练中使用的损失函数。可以认为，拍卖设计是卖家设计博弈规则，买家参与博弈。前述工作主要使用机器学习来增强卖家，同时假设买家是理性的，也就是说买家能够找到自己的最优出价。确切地说，在收入最大化拍卖机制中，收入的定义是基于每个买家的出价都遵循纳什均衡的假设，而显示原理又将纳什均衡进一步转换为真实的出价。然而，在实践中，买家可能无法找到这个均衡。因此，拍卖机制应用于现实世界之前，拍卖设计必须考虑非理性的买家，尤其是学习式参与者。引入机器学习方法求解组合优化问题，当前仍面临一些限制与挑战。本节先通过组合优化与模式识别的比较，引出组合优化中应用机器学习的若干困难。之后提出，在当前研究中，增强算法还有哪些属性问题有待解决。下文通过与模式识别比较，总结机器学习引入到组合优化中所面临的困难。1.难以构造高质量的训练数据集。如今，要训练出性能良好的机器学习模型，通常需要大规模的训练数据集，因此获得高质量的数据集至关重要。在模式识别中，数据点通常由特征和标签组成。有几种成本可接受的方法可用来获取训练数据，比如雇佣人工来打标签。但是，组合优化实例的标签通常就是最优解。计算最优解的成本高昂，对于大规模实例尤其如此，而且不太可能像模式识别中那样由人工来打“标签”。因此，构建包含不同规模实例的高质量数据集是一大挑战。2.对扰动和噪声的敏感性。在模式识别中，鲁棒性是对机器学习模型的一项关键要求，也就是说，机器学习模型不应对小的扰动或噪声过于敏感。为提高所学到的机器学习模型的鲁棒性，可以在维护标签时轻微扰动训练数据。但是，组合优化问题却具有很高的敏感性，即使微小的扰动或噪声都可能对问题的最优解产生影响。以旅行商问题为例，添加单条边就会改变最优解，比如图 4 中，添加边(A,D)导致最优解中一半的边发生了改变。SAT 问题也存在同样的敏感性，在问题中添加子句可能使可满足状态改变为不可满足。此外，在 CSP 问题中，添加一条约束或从问题的约束关系中删除一个元组，原本容易满足的问题就可能变得难以满足。组合优化的这种敏感性也导致难以构建高质量的训练数据集，因为无法像模式识别那样通过小的扰动来构建不同的实例。因此，我们希望学习到的机器学习模型能够识别这种敏感性，但这一要求不同于模式识别，带来很大的挑战。71|华为研究2022 年 12 月软件理论6.2 增强算法的期望属性将机器学习纳入组合优化，尽管相关研究已取得一些进展，但在增强算法的设计上仍存在许多挑战。挑战体现在多个方面，包括组合优化的具体性质、对理论或启发式方法缺乏理解，以及现实的需求。1.扩展性。构建大规模训练数据的难度很大。因此，为组合优化问题训练机器学习模型时，目前通常使用小规模的数据集，比如最多 1000 个变量。然而，研究人员仍希望设计出增强的算法，使算法在输入规模较大时也具备良好的性能。这使机器学习模型的扩展性成为关注的焦点，在新近的几次调研中 114,87,19，扩展性已被列为未来的研究方向。已有部分工作 111,68,90 尝试扩展到规模大得多的实例。不过，现有的很多增强框架并不具备良好的扩展性，当实例规模增加时，解的质量会迅速下降 114。2.适应性。与经典的组合优化问题不同，实际的应用场景通常涉及额外的目标或约束。为减少问题变化时重新设计算法的成本，学习到的增强框架应能适应问题集内的数据扰动，或适配同一问题族中的其他问题。已有一些初步工作 96 对机器学习模型的适应性开展了研究。3.理论保证。传统的理论算法通常具有执行时间、近似比和泛化界限等方面的可证明保证。在引入机器学习算法时，应尽量不影响已有的理论保证，这样可以提高所学模型的可解释性，但要做到这一点挑战很大。执行时间与模型性能一样，都与算法的实现密切相关。增强算法从设计上应减少算法运行时间，同时不影响输出解的质量。已有初步研究 17,72 用更少的时间实现了相近的求解性能，提升了机器学习模型的效率。然而，这些研究提供的框架只能处理 100 个节点，远未达到最先进的水平。图 4 旅行商问题的敏感性示例近似比是对输出解质量的理论保证。实现近似保证的一种方法是将近似算法与机器学习方法结合起来，例如在顶点覆盖问题和旅行商问题 68 中的组合应用。然而，现有的组合通常只考虑基本的理论方法或启发式方法，比如贪心算法或分支限界算法。因此有必要进一步考察其他近似算法，虽然这些算法可能更复杂，但它们具有更好的近似比。机器学习方法如果与更好的近似算法结合运用，可以提供更佳的近似保证。泛化能力反映所学模型能否在其他一般性实例上表现良好，体现模型的实用价值。传统理论算法考虑的是最坏情况界限，因而自然地满足泛化要求。然而，机器学习学到的模型通常依赖特定的训练数据集，其泛化能力就成为机器学习的重要课题。因此，有必要进一步研究，在引入机器学习方法的同时，如何保持模型的泛化能力。样本复杂度与上述所有因素相关。样本的数量通常决定训练花费的时长以及所学模型的质量，模型质量又可能影响增强算法的近似比。此外，如果训练数据和测试数据是从相同分布中提取的，那么泛化界限通常与从训练数据集估得的基础分布好坏程度有关，而这很大程度上取决于样本复杂度。华为研究|722022 年 12 月1 Dimitris Achlioptas,Marek Chrobak,and John Noga.Competitive analysis of randomized paging algorithms.Theoretical Computer Science,234(1-2):203218,2000.2 Gagan Aggarwal,Gagan Goel,Chinmay Karande,and Aranyak Mehta.Online vertex-weighted bipartite matching and single-bid budgeted allocations.In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms,pages 12531264.SIAM,2011.3 Antonios Antoniadis,Christian Coester,Marek Elias,Adam Polak,and Bertrand Simon.Online metric algorithms with untrusted predictions.In International Conference on Machine Learning,pages 345355.PMLR,2020.4 Antonios Antoniadis,Themis Gouleakis,Pieter Kleer,and Pavel Kolev.Secretary and online matching problems with machine learned advice.In 34th Conference on Neural Information Processing Systems.Curran Associates,Inc.,2020.5 Sanjeev Arora.Polynomial time approximation schemes for Euclidean travelling salesman and other geometric problems.Journal of the ACM(JACM),45(5):753782,1998.6 Ashwinkumar Badanidiyuru,Shahar Dobzinski,Hu Fu,Robert Kleinberg,Noam Nisan,and Tim Roughgarden.Sketching valuation functions.In Yuval Rabani,editor,Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms,SODA 2012,Kyoto,Japan,January 17-19,2012,pages 10251035.7 Yunsheng Bai,Derek Xu,Alex Wang,Ken Gu,Xueqing Wu,Agustin Marinovic,Christopher Ro,Yizhou Sun,and Wei Wang.Glsearch:Maximum common subgraph detection via learning to search.CoRR,abs/2002.03129,2020.8 Maria-Florina Balcan and Nicholas J.A.Harvey.Learning submodular functions.In Peter A.Flach,Tijl De Bie,and Nello Cristianini,editors,Machine Learning and Knowledge Discovery in Databases-European Conference,ECML PKDD 2012,Bristol,参考文献UK,September 24-28,2012.Proceedings,Part II,volume 7524 of Lecture Notes in Computer Science,pages 846849.Springer,2012.9 Eric Balkanski,Nicole Immorlica,and Yaron Singer.The importance of communities for learning to influence.In Isabelle Guyon,Ulrike von Luxburg,Samy Bengio,Hanna M.Wallach,Rob Fergus,S.V.N.Vishwanathan,and Roman Garnett,editors,Advances in Neural Information Processing Systems 30:Annual Conference on Neural Information Processing Systems 2017,December 4-9,2017,Long Beach,CA,USA,pages 58625871,2017.10 Eric Balkanski,Aviad Rubinstein,and Yaron Singer.The power of optimization from samples.In Daniel D.Lee,Masashi Sugiyama,Ulrike von Luxburg,Isabelle Guyon,and Roman Garnett,editors,Advances in Neural Information Processing Systems 29:Annual Conference on Neural Information Processing Systems 2016,December 5-10,2016,Barcelona,Spain,pages 40174025,2016.11 Eric Balkanski,Aviad Rubinstein,and Yaron Singer.The limitations of optimization from samples.In Hamed Hatami,Pierre McKenzie,and Valerie King,editors,Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing,STOC 2017,Montreal,QC,Canada,June 19-23,2017,pages 10161027.ACM,2017.12 Eric Balkanski and Yaron Singer.Minimizing a submodular function from samples.In Isabelle Guyon,Ulrike von Luxburg,Samy Bengio,Hanna M.Wallach,Rob Fergus,S.V.N.Vishwanathan,and Roman Garnett,editors,Advances in Neural Information Processing Systems 30:Annual Conference on Neural Information Processing Systems 2017,December 4-9,2017,Long Beach,CA,USA,pages 814822,2017.13 Eric Balkanski and Yaron Singer.The sample complexity of optimizing a convex function.In Satyen Kale and Ohad Shamir,editors,Proceedings of the 30th Conference on Learning Theory,COLT 2017,Amsterdam,The Netherlands,7-10 July 2017,volume 65 of Proceedings of Machine Learning Research,pages 275301.PMLR,2017.14 Radu Baltean-Lugojan,Pierre Bonami,Ruth Misener,73|华为研究2022 年 12 月软件理论and Andrea Tramontani.Selecting cutting planes for quadratic semidefinite outer-approximation via trained neural networks.Technical Report,Imperial College,London,2018.15 Nikhil Bansal,Kedar Dhamdhere,Jochen Knemann,and Amitabh Sinha.Non-clairvoyant scheduling for minimizing mean slowdown.Algorithmica,40(4):305318,2004.16 Luca Becchetti and Stefano Leonardi.Non-clairvoyant scheduling to minimize the average flow time on single and parallel machines.In Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing,pages 94103,2001.17 Irwan Bello,Hieu Pham,Quoc V.Le,Mohammad Norouzi,and Samy Bengio.Neural combinatorial optimization with reinforcement learning.In 5th International Conference on Learning Representations,ICLR 2017,Toulon,France,April 24-26,2017,Workshop Track Proceedings.OpenR,2017.18 Alberto Bemporad and Vihangkumar V.Naik.A numerically robust mixed-integer quadratic programming solver for embedded hybrid model predictive control.IFAC-PapersOnLine,51:412417,2018.19 Yoshua Bengio,Andrea Lodi,and Antoine Prouvost.Machine learning for combinatorial optimization:A methodological tour dhorizon.European Journal of Operational Research,2020.20 Bernd Bischl,Pascal Kerschke,Lars Kotthoff,Marius Lindauer,Yuri Malitsky,Alexandre Frchette,Holger Hoos,Frank Hutter,Kevin Leyton-Brown,Kevin Tierney,et al.Aslib:A benchmark library for algorithm selection.Artificial Intelligence,237:4158,2016.21 Pierre Bonami,Andrea Lodi,and Giulia Zarpellon.Learning a classification of mixed-integer quadratic programming problems.In International Conference on the Integration of Constraint Programming,Artificial Intelligence,and Operations Research,pages 595604.Springer,2018.22 Qingpeng Cai,Aris Filos-Ratsikas,Pingzhong Tang,and Yiwei Zhang.Reinforcement mechanism design for e-commerce.In Proceedings of the 2018 World Wide Web Conference,WWW 18,page 13391348,Republic and Canton of Geneva,CHE,2018.International World Wide Web Conferences Steering Committee.23 Wei Chen,Xiaoming Sun,Jialin Zhang,and Zhijie Zhang.Optimization from structured samples for coverage functions.In Proceedings of the 37th International Conference on Machine Learning,ICML 2020,13-18 July 2020,Virtual Event,volume 119 of Proceedings of Machine Learning Research,pages 17151724.PMLR,2020.24 Wei Chen,Xiaoming Sun,Jialin Zhang,and Zhijie Zhang.Network inference and influence maximization from samples.In Marina Meila and Tong Zhang,editors,Proceedings of the 38th International Conference on Machine Learning,ICML 2021,18-24 July 2021,Virtual Event,volume 139 of Proceedings of Machine Learning Research,pages 17071716.PMLR,2021.25 Nicos Christofides.Worst-case analysis of a new heuristic for the travelling salesman problem.Technical report,Carnegie-Mellon Univ Pittsburgh Pa Management Sciences Research Group,1976.26 Graham Cormode and S Muthukrishnan.Space efficient mining of multigraph streams.In Proceedings of the Twenty-Fourth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems,pages 271282,2005.27 Janos Csirik,David S Johnson,Claire Kenyon,James B Orlin,Peter W Shor,and Richard R Weber.On the sum-of-squares algorithm for bin packing.Journal of the ACM(JACM),53(1):165,2006.28 George B Dantzig.Maximization of a linear function of variables subject to linear inequalities.Activity Analysis of Production and Allocation,13:339347,1951.29 Xiaotie Deng,Xinyan Hu,Tao Lin,and Weiqiang Zheng.Nash convergence of mean-based learning algorithms in first price auctions,2021.30 Michel Deudon,Pierre Cournut,Alexandre Lacoste,Yossiri Adulyasak,and Louis-Martin Rousseau.Learning heuristics for the TSP by policy gradient.In International Conference on the Integration of Constraint Programming,Artificial Intelligence,and 华为研究|742022 年 12 月Operations Research,pages 170181.Springer,2018.31 Nikhil R Devanur and Thomas P Hayes.The adwords problem:Online keyword matching with budgeted bidders under random permutations.In Proceedings of the 10th ACM Conference on Electronic Commerce,pages 7178,2009.32 Marco Dorigo,Mauro Birattari,and Thomas Stutzle.Ant colony optimization.IEEE Computational Intelligence Magazine,1(4):2839,2006.33 Marco Dorigo and Gianni Di Caro.Ant colony optimization:A new meta-heuristic.In Proceedings of the 1999 Congress on Evolutionary Computation-CEC99(Cat.No.99TH8406),volume 2,pages 14701477.IEEE,1999.34 Lu Duan,Haoyuan Hu,Yu Qian,Yu Gong,Xiaodong Zhang,Jiangwen Wei,and Yinghui Xu.A multi-task selected learning approach for solving 3D flexible bin packing problem.In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems,pages 13861394,2019.35 Zhijian Duan,Dinghuai Zhang,Wenhan Huang,Yali Du,Yaodong Yang,Jun Wang,and Xiaotie Deng.PAC learnability of approximate Nash equilibrium in bimatrix games,2021.36 Paul Duetting,Zhe Feng,Harikrishna Narasimhan,David Parkes,and Sai Srivatsa Ravindranath.Optimal auctions through deep learning.In Kamalika Chaudhuri and Ruslan Salakhutdinov,editors,Proceedings of the 36th International Conference on Machine Learning,volume 97 of Proceedings of Machine Learning Research,pages 17061715.PMLR,0915 Jun 2019.37 Evgenii Borisovich Dynkin.The optimum choice of the instant for stopping a Markov process.Soviet Mathematics,4:627629,1963.38 Zhe Feng,Harikrishna Narasimhan,and David C.Parkes.Deep learning for revenue-optimal auctions with budgets.In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems,AAMAS 18,page 354362,Richland,SC,2018.International Foundation for Autonomous Agents and Multiagent Systems.39 Thomas A Feo and Mauricio GC Resende.Greedy randomized adaptive search procedures.Journal of Global Optimization,6(2):109133,1995.40 Merrill M Flood.The travelling-salesman problem.Operations Research,4(1):6175,1956.41 Alex S Fukunaga and Richard E Korf.Bin completion algorithms for multicontainer packing,knapsack,and covering problems.Journal of Artificial Intelligence Research,28:393429,2007.42 Fred Glover.Tabu search:part i.ORSA Journal on Computing,1(3):190206,1989.43 Fred Glover.Tabu search:part ii.ORSA Journal on Computing,2(1):432,1990.44 Fred Glover and Manuel Laguna.Tabu search.In Handbook of Combinatorial Optimization,pages 20932229.Springer,1998.45 Fred Glover,Manuel Laguna,and Rafael Mart.Fundamentals of scatter search and path relinking.Control and Cybernetics,29(3):653684,2000.46 David E Goldberg.Genetic Algorithms.Pearson Education India,2006.47 Noah Golowich,Harikrishna Narasimhan,and David C.Parkes.Deep learning for multi-facility location mechanism design.In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence,IJCAI-18,pages 261267.International Joint Conferences on Artificial Intelligence Organization,7 2018.48 Avinatan Hassidim and Yaron Singer.Submodular optimization under noise.In Satyen Kale and Ohad Shamir,editors,Proceedings of the 30th Conference on Learning Theory,COLT 2017,Amsterdam,The Netherlands,7-10 July 2017,volume 65 of Proceedings of Machine Learning Research,pages 10691122.PMLR,2017.49 He He,Hal Daume III,and Jason M Eisner.Learning to search in branch and bound algorithms.In Z.Ghahramani,M.Welling,C.Cortes,N.Lawrence,and K.Q.Weinberger,editors,Advances in Neural Information Processing Systems,volume 27.Curran Associates,Inc.,2014.75|华为研究2022 年 12 月软件理论50 Michael Held and Richard M Karp.A dynamic programming approach to sequencing problems.Journal of the Society for Industrial and Applied mathematics,10(1):196210,1962.51 Holger H Hoos.Automated algorithm configuration and parameter tuning.In Autonomous Search,pages 3771.Springer,2011.52 Andre Hottung,Shunji Tanaka,and Kevin Tierney.Deep learning assisted heuristic tree search for the container pre-marshalling problem.Computers&Operations Research,113:104781,2020.53 Chen-Yu Hsu,Piotr Indyk,Dina Katabi,and Ali Vakilian.Learning-based frequency estimation algorithms.In International Conference on Learning Representations,2018.54 Sungjin Im,Janardhan Kulkarni,and Kamesh Munagala.Competitive algorithms from competitive equilibria:Non-clairvoyant scheduling under polyhedral constraints.Journal of the ACM(JACM),65(1):133,2017.55 Sungjin Im,Janardhan Kulkarni,Kamesh Munagala,and Kirk Pruhs.Selfishmigrate:A scalable algorithm for non-clairvoyantly scheduling heterogeneous processors.In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science,pages 531540.IEEE,2014.56 Sungjin Im,Ravi Kumar,Mahshid Montazer Qaem,and Manish Purohit.Non-clairvoyant scheduling with predictions.In Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures,pages 285294,2021.57 Piotr Indyk.Stable distributions,pseudorandom generators,embeddings,and data stream computation.Journal of the ACM(JACM),53(3):307323,2006.58 Piotr Indyk and David Woodruff.Optimal approximations of the frequency moments of data streams.In Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing,pages 202208,2005.59 Thathachar S Jayram and David P Woodruff.The data stream space complexity of cascaded norms.In 2009 50th Annual IEEE Symposium on Foundations of Computer Science,pages 765774.IEEE,2009.60 Tanqiu Jiang,Yi Li,Honghao Lin,Yisong Ruan,and David P Woodruff.Learning-augmented data stream algorithms.In International Conference on Learning Representations,2019.61 Daniel M Kane,Jelani Nelson,and David P Woodruff.An optimal algorithm for the distinct elements problem.In Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems,pages 4152,2010.62 Daniel Karapetyan,Abraham P Punnen,and Andrew J Parkes.Markov chain methods for the bipartite boolean quadratic programming problem.European Journal of Operational Research,260(2):494506,2017.63 Anna R.Karlin,Mark S.Manasse,Lyle A.McGeoch,and Susan Owicki.Competitive randomized algorithms for nonuniform problems.Algorithmica,11(6):542571,1994.64 Narendra Karmarkar.A new polynomial-time algorithm for linear programming.In Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing,pages 302311,1984.65 Marek Karpinski,Michael Lampis,and Richard Schmied.New inapproximability bounds for TSP.Journal of Computer and System Sciences,81(8):16651677,2015.66 Thomas Kesselheim,Klaus Radke,Andreas Tnnis,and Berthold Vcking.An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions.In European Symposium on Algorithms,pages 589600.Springer,2013.67 Leonid Genrikhovich Khachiyan.A polynomial algorithm in linear programming.In Doklady Akademii Nauk.Russian Academy of Sciences,1979.68 Elias Khalil,Hanjun Dai,Yuyu Zhang,Bistra Dilkina,and Le Song.Learning combinatorial optimization algorithms over graphs.In Advances in Neural Information Processing Systems,pages 63486358,2017.华为研究|762022 年 12 月69 Scott Kirkpatrick,C Daniel Gelatt,and Mario P Vecchi.Optimization by simulated annealing.Science,220(4598):671680,1983.70 Victor Klee and George J Minty.How good is the simplex algorithm.Inequalities,3(3):159175,1972.71 Wouter Kool,Herke van Hoof,and Max Welling.Attention,learn to solve routing problems!In International Conference on Learning Representations,2018.72 Wouter Kool,Herke van Hoof,and Max Welling.Attention,learn to solve routing problems!In 7th International Conference on Learning Representations,ICLR 2019,New Orleans,LA,USA,May 6-9,2019.OpenR,2019.73 Nitish Korula and Martin Pl.Algorithms for secretary problems on graphs and hypergraphs.In International Colloquium on Automata,Languages,and Programming,pages 508520.Springer,2009.74 Markus Kruber,Marco E Lbbecke,and Axel Parmentier.Learning when to use a decomposition.In International Conference on AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems,pages 202210.Springer,2017.75 Eugene L Lawler.The travelling salesman problem:A guided tour of combinatorial optimization.Wiley-Interscience Series in Discrete Mathematics,1985.76 Zhuwen Li,Qifeng Chen,and Vladlen Koltun.Combinatorial optimization with graph convolutional networks and guided tree search.In S.Bengio,H.Wallach,H.Larochelle,K.Grauman,N.Cesa-Bianchi,and R.Garnett,editors,Advances in Neural Information Processing Systems,volume 31.Curran Associates,Inc.,2018.77 Denis V Lindley.Dynamic programming and decision theory.Journal of the Royal Statistical Society:Series C(Applied Statistics),10(1):3951,1961.78 Xiangyu Liu,Chuan Yu,Zhilin Zhang,Zhenzhe Zheng,Yu Rong,Hongtao Lv,Da Huo,Yiqing Wang,Dagui Chen,Jian Xu,Fan Wu,Guihai Chen,and Xiaoqiang Zhu.Neural auction:End-to-end learning of auction mechanisms for e-commerce advertising.KDD 21,page 33543364,New York,NY,USA,2021.Association for Computing Machinery.79 Yanli Liu,Chu-Min Li,Hua Jiang,and Kun He.A learning based branch and bound for maximum common subgraph related problems.Proceedings of the AAAI Conference on Artificial Intelligence,34:23922399,04 2020.80 Andrea Lodi and Giulia Zarpellon.On learning and branching:A survey.Top,25(2):207236,2017.81 Michele Lombardi and Michela Milano.Boosting combinatorial problem modeling with machine learning.arXiv preprint arXiv:1807.05517,2018.82 Helena R Loureno,Olivier C Martin,and Thomas Sttzle.Iterated local search.In Handbook of Metaheuristics,pages 320353.Springer,2003.83 Thodoris Lykouris and Sergei Vassilvtiskii.Competitive caching with machine learned advice.In International Conference on Machine Learning,pages 32963305.PMLR,2018.84 Qiang Ma,Suwen Ge,Danyang He,Darshan Thaker,and Iddo Drori.Combinatorial optimization by graph pointer networks and hierarchical reinforcement learning.arXiv preprint arXiv:1911.04936,2019.85 Franco Mascia,Manuel Lpez-Ibez,Jrmie Dubois-Lacoste,and Thomas Sttzle.Grammar-based generation of stochastic local search heuristics through automatic algorithm configuration tools.Computers&Operations Research,51:190199,2014.86 Daniele Masti and Alberto Bemporad.Learning binary warm starts for multiparametric mixed-integer quadratic programming.pages 14941499,06 2019.87 Nina Mazyavkina,Sergey Sviridov,Sergei Ivanov,and Evgeny Burnaev.Reinforcement learning for combinatorial optimization:A survey.arXiv preprint arXiv:2003.03600,2020.88 Jesper W Mikkelsen.Randomization can be as helpful as a glimpse of the future in online computation.In 43rd International Colloquium on Automata,Languages,and Programming(ICALP 2016).Schloss Dagstuhl-Leibniz-Zentrum fr Informatik,2016.77|华为研究2022 年 12 月软件理论89 Joseph SB Mitchell.Guillotine subdivisions approximate polygonal subdivisions:A simple polynomial-time approximation scheme for geometric TSP,k-MST,and related problems.SIAM Journal on Computing,28(4):12981309,1999.90 Akash Mittal,Anuj Dhawan,Sahil Manchanda,Sourav Medya,Sayan Ranu,and Ambuj Singh.Learning heuristics over large graphs via deep reinforcement learning.arXiv preprint arXiv:1903.03332,2019.91 Michael Mitzenmacher and Sergei Vassilvitskii.Algorithms with predictions.arXiv preprint arXiv:2006.09123,2020.92 Nenad Mladenovi and Pierre Hansen.Variable neighborhood search.Computers&Operations Research,24(11):10971100,1997.93 Rajeev Motwani,Steven Phillips,and Eric Torng.Nonclairvoyant scheduling.Theoretical Computer Science,130(1):1747,1994.94 Katta G Murty.Computational complexity of parametric linear programming.Mathematical Programming,19(1):213219,1980.95 Roger B Myerson.Optimal auction design.Mathematics of Operations Research,6(1)5873,1981.96 Mohammadreza Nazari,Afshin Oroojlooy,Lawrence Snyder,and Martin Takc.Reinforcement learning for solving the vehicle routing problem.In Advances in Neural Information Processing Systems,pages 98399849,2018.97 Denis Nekipelov,Vasilis Syrgkanis,and Eva Tardos.Econometrics for learning agents.In Proceedings of the Sixteenth ACM Conference on Economics and Computation,EC 15,page 118,New York,NY,USA,2015.Association for Computing Machinery.98 George L.Nemhauser,Laurence A.Wolsey,and Marshall L.Fisher.An analysis of approximations for maximizing submodular set functions-I.Math.Program.,14(1):265294,1978.99 Alex Nowak,Soledad Villar,Afonso S Bandeira,and Joan Bruna.A note on learning algorithms for quadratic assignment with graph neural networks.In Proceeding of the 34th International Conference on Machine Learning(ICML),volume 1050,page 22,2017.100 Pekka Orponen and Heikki Mannila.On Approximation Preserving Reductions:Complete Problems and Robust Measures.Citeseer,1987.101 Manfred Padberg and Giovanni Rinaldi.A branch-and-cut algorithm for the resolution of large-scale symmetric travelling salesman problems.SIAM Review,33(1):60100,1991.102 Marcelo Prates,Pedro HC Avelar,Henrique Lemos,Luis C Lamb,and Moshe Y Vardi.Learning to solve NP-complete problems:A graph neural network for decision TSP.In Proceedings of the AAAI Conference on Artificial Intelligence,volume 33,pages 47314738,2019.103 Manish Purohit,Zoya Svitkina,and Ravi Kumar.Improving online algorithms via ML predictions.In Advances in Neural Information Processing Systems,pages 96619670,2018.104 Manish Purohit,Zoya Svitkina,and Ravi Kumar.Improving online algorithms via ML predictions.In S.Bengio,H.Wallach,H.Larochelle,K.Grauman,N.Cesa-Bianchi,and R.Garnett,editors,Advances in Neural Information Processing Systems,volume 31.Curran Associates,Inc.,2018.105 Jad Rahme,Samy Jelassi,and S.Matthew Weinberg.Auction learning as a two-player game.In International Conference on Learning Representations,2021.106 Dhruv Rohatgi.Near-optimal bounds for online caching with machine learned advice.In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms,pages 18341845.SIAM,2020.107 Nir Rosenfeld,Eric Balkanski,Amir Globerson,and Yaron Singer.Learning to optimize combinatorial functions.In Jennifer G.Dy and Andreas Krause,editors,Proceedings of the 35th International Conference on Machine Learning,ICML 2018,Stockholmsmssan,Stockholm,Sweden,July 10-15,2018,volume 80 of Proceedings of Machine Learning Research,pages 43714380.华为研究|782022 年 12 月118 Jiongzhi Zheng,Kun He,Jianrong Zhou,Yan Jin,and Chu-Min Li.Combining reinforcement learning with Lin-Kernighan-Helsgaun algorithm for the traveling salesman problem.CoRR,abs/2012.04461,2020.108 Francesca Rossi,Peter van Beek,and Toby Walsh.Handbook of Constraint Programming(Foundations of Artificial Intelligence).Elsevier Science Inc.,USA,2006.109 Yuko Sakurai,Satoshi Oyama,Mingyu Guo,and Makoto Yokoo.Deep False-Name-Proof Auction Mechanisms,pages 594601.10 2019.110 Ethan L Schreiber and Richard E Korf.Improved bin completion for optimal bin packing and number partitioning.In Twenty-Third International Joint Conference on Artificial Intelligence,2013.111 Daniel Selsam,Matthew Lamm,Benedikt Bnz,Percy Liang,Leonardo de Moura,and David L Dill.Learning a SAT solver from single-bit supervision.arXiv preprint arXiv:1802.03685,2018.112 Weiran Shen,Pingzhong Tang,and Song Zuo.Automated Mechanism Design via Neural Networks,page 215223.International Foundation for Autonomous Agents and Multiagent Systems,Richland,SC,2019.113 Daniel A Spielman and Shang-Hua Teng.Smoothed analysis of algorithms Why the simplex algorithm usually takes polynomial time.Journal of the ACM(JACM),51(3):385463,2004.114 Natalia Vesselinova,Rebecca Steinert,Daniel F Perez-Ramirez,and Magnus Boman.Learning combinatorial optimization on graphs:A survey with applications to networking.arXiv preprint arXiv:2005.11081,2020.115 Alexander Wei.Better and simpler learning-augmented online caching.In Approximation,Randomization,and Combinatorial Optimization.Algorithms and Techniques(APPROX/RANDOM 2020).Schloss Dagstuhl-Leibniz-Zentrum fr Informatik,2020.116 Gerhard J Woeginger.Exact algorithms for NP-hard problems:A survey.In Combinatorial Optimization:Eureka,You Shrink!,pages 185207.Springer,2003.117 Yaoxin Wu,Wen Song,Zhiguang Cao,Jie Zhang,and Andrew Lim.Learning improvement heuristics for solving the travelling salesman problem.arXiv preprint arXiv:1912.05784,2019.79|华为研究2022 年 12 月软件理论可满足性（Boolean Satisfiability，SAT）问题在计算机科学中相当重要。很多启发式算法可用于求解可满足性问题，但这些算法基于实验方式来评估，缺乏理论分析。本文将主要关注随机游走（Random Walk，RW）技术，并结合适应度函数，提升随机游走的性能。这种改进版的 RW 被称为 RWF。为了验证 RWF 的性能，我们基于三种 SAT 表达式，分析比较了 RW、(1 1)EA（一种典型的演化算法）和 RWF 的期望运行时间。结果表明，RWF 在部分实例上的性能优于 RW 和(1 1)EA。关键词布尔可满足性，随机游走，运行时间分析摘要蔡少伟，姜滔中国科学院软件研究所计算机科学国家重点实验室随机游走与适应度函数相结合求解布尔可满足性问题华为研究|802022 年 12 月1 引言布尔可满足性（Boolean Satisfiability，SAT）问题是指，确定是否存在使给定命题表达式为真的变量赋值的问题，是计算机科学中相当重要的一类问题。SAT 问题是第一个被证明为 NP 完全的问题，这意味着其他 NP 复杂度分类下的问题的求解难度不会超过 SAT 问题。除了理论上的重要地位，SAT 算法还在硬件验证、密码学、资源分配和规划等领域有着广泛的实际应用。SAT 问题在理论上极具挑战性，尚无高效的求解算法。简单穷举算法可以穷尽n个变量的2n个取值，得到O(2n)的平凡边界，但迄今还没新的算法能突破这一界限。实际上，强指数时间假设（Strong Exponential Time Hypothesis，SETH）认为，当常数c fitness(x)，则 x:=y5:end while以下算法将 RW 方法和适应度函数相结合，是我们分析的重点。该算法每一步用一个适应值来引导搜索。算法 3 带适应度函数的随机游走(RWF)算法1:随机选取一个初始比特串x；2:while 表达式未满足 do 3:随机选取一个未满足的子句c；4:随机选取c中的一个变量并翻转其值，得到解y；5:若 fitness(y)fitness(x)，则 x:=y6:end while3.2 RW 与 RWF 算法对比本节分析了 RW 和 RWF 两种算法求解两个不同 SAT实例的时间复杂度（平均情况和最坏情况），以便从理论上认识这两种算法。实 例 3.2.1 设x=(x1xn)0,1n，SAT 实 例1(x)定义为满足条件的赋值为(00)和(11)。命题 3.2.1 在 SAT 实例1上，RW 的期望运行时间为|m|1=(n2)。证明：参见12。命题 3.2.2 在 SAT 实例1上，RWF 的期望运行时间为|m|1=O(n)。证明：本文后续内容中，对于任意赋值x，用|x|来表示x中“1”的数量。根据式（1），1的适应度函数为fit1(x)=2(n 1)|x|,x=(0)n 1 |x|1,x=(1)1(x)=(x1 x2)(x1 xn)(x1 x2)(x1 xn)fit(x)=c1(x) c2(x) cm(x)(1)华为研究|822022 年 12 月该 适 应 度 函 数 只 与x1和|x|相 关。具 体 来 说，若x=(0)，函数随|x|单调下降，否则单调增加。图 1为n=20时适应度函数fit1(x)的图像。简单起见，设n为偶数。将搜索空间S划分为2n个子空间：令Xt 0,1n(t=0,1,.)为随机变量，用于表示RWF 算法求解 SAT 实例1时，在时间t所处的状态，则转移概率描述如下。当k=0，有 当1 k n2 1，对于Xt S0,k，未满足子句的形式为x1 xi。若算法使x1为 1，适应度函数下降，该突变不会被保留。当n2 k n 1，对于 Xt S0,k，未满足子句的形式为x1 xi。如果算法使x1为 1，适应度函数上升，该突变将被保留。图 1 n=20的适应度函数fit1(x)S0,k=x|x=(0),|x|=k(k=0,.,n 1)S1,k=x|x=(1),|x|=k(k=1,.,n)P(Xt 1 S0,k|Xt S0,k)=12P(Xt 1 S0,k1|Xt S0,k)=12P(Xt 1 S0,k|Xt S0,k)=1P(Xt 1 S0,k1|Xt S0,k)=12P(Xt 1 S1,k 1|Xt S0,k)=12同理可得：当k=n，有当n2 1 k n 1，有当1 k n2，有引入具有状态空间z0,0,z0,1,.,z0,n1;z1,1,z1,2,.,z1,n的辅助齐次马尔可夫链Zt(t=0,1,.)，则转移概率定义为式中，u,v 0,1且h,k 0,.,n。此时，Zt就是一个吸收马尔可夫链，其吸收状态为z0,0和z1,n。对于任意x Su,k(u 0,1,k 0,.,n)，平均首次到达时间mx等于mzu,k。根据吸收马尔可夫链理论，随机过程Zt的平均首次到达时间表示为接下来，需要证明m0,k 2kn2 k n 1当k=n2，有P(Xt 1 S1,k|Xt S1,k)=1P(Xt 1 S1,k|Xt S1,k)=12P(Xt 1 S1,k 1|Xt S1,k)=12P(Xt 1 S0,k1|Xt S1,k)=12P(Xt 1 S1,k 1|Xt S1,k)=12P(Zt 1=zv,h|Zt=zu,k)=P(Xt 1 Sv,h|Xt Su,k)m0,k=2k1 k n2 1m0,k=12(m0,k1 1) 12(m1,k 1 1)n2 k n 1m1,k=2(n k)n2 1 k n 1m1,k,=12(m0,k1 1) 12(m1,k 1 1)1 k n2m0,n2=12(m0,n21 1) 12(m1,n2 1 1)=12(2(n2 1) 1) 12(2(n2 1) 1)=n 1式中83|华为研究2022 年 12 月软件理论对于|x|=k，SAT 实例2的适应度函数为该函数是一个关于k的二阶多项式。如果 RWF 选取的初始解为x(|x|n 12)，根据 RWF 的搜索过程，可得到局部最优解(0,.,0)，而非全局最优解(1,.,1)。当k n 12时，始于Sk的 RWF 算法永远无法达到满足条件的赋值(1,.,1)，因为适应度随着|x|的增加而降低。当k n 12，有根据期望的定义：至此，证明结束。先前的结果中，RWF 在 SAT 实例1上的期望运行时间优于 RW。而在 SAT 实例2上，RW 的期望运行时间优于 RWF，与先前的结果相反。我们注意到，用 RW 算法求解 SAT 问题，求解过程的分析高度依赖于适应度函数。由于适应度函数表达式在书写上存在障碍，对于一般性 SAT 问题的求解，要分析RWF 算法的期望运行时间非常困难。接下来，我们构造一个 SAT 实例3(x)，在不书写适应度函数表达式的情况下来分析 RWF 算法的期望运行时间。3.3 RW、局部(1 1)EA 和 RWF 算法对比实例 3.3.1 对于x=(x1xn)0,1n，SAT 实例3(x)由以下子句构成：(x1 x2),(x1 xn),(x1 x2)(x1 xn),(x1 x2),(x1 xn),(x1 x2)(x1 xn),可得k=n2时，m0,k 2k成立。假设k n2时该结论也成立（即m0,k 2k），则有进而可得m0,k 1 k n k 1 2(k 1)k n2对于m1,k，可得出类似结论，概括如下：因此，|m|1=O(n)。对于 SAT 实例1，RWF 的期望运行时间边界O(n)优于 RW 的O(n2)。然而，下面另一个 SAT 实例2中，在一定条件下会出现相反的结果。实例 3.2.2 SAT 实例2具有以下子句xi,xi xji,j 1,.,n,i=jSAT 实例2唯一满足条件的赋值为(1,.,1)。命题 3.2.3 对于 SAT 实例2，RW 的期望运行时间为|m|=(n2)。证明：参见 12。命题 3.2.4 RWF 在 SAT 实例2上的期望运行时间为证明：首先，将搜索空间划分为n 1个子空间：满足条件的集合为Sn。m0,k 1=12(m0,k 1) 12(m1,k 2 1)=12m0,k n k 1m0,k 2k0 k n 1m1,k 2(n k)1 k nmi= ,i Product-Profit-Project）这样的商业闭环，并不断推动开源的可持续发展。当今企业拥抱开源已经不单纯是为了降低成本、快速开发新产品尽管这还是很多企业的主要动机（图 1）近年来，随着生态经济、行业数字化转型、软件定义一切的发展，越来越多的企业希望通过主动开源来加速上述目标的实现（图 2）。1 引言2 开源策略的制定2.1 要素一：商业模式图 1 OSSRA 各行业使用开源占比图 2 垂直行业主动开源占比本文从企业开源策略的制定、企业级开源社区的构建等方面阐述企业如何利用开源来发展生态经济、推动行业数字化转型，并提出面向社区开发者和管理者的社区度量方法，以支撑企业构建高成长性、高粘性的开源社区，实现其开源战略。一般情况下，开源策略的制定需要考虑如下六个要素3：商业模式、知识产权策略、开源技术策略、项目治理与社区平台策略、生态构建策略、成功度衡量。在这六个维度中，前五个将是本节阐述的主要内容，而最后一个维度则在第 3 节“社区构建的度量”中着重阐述。开源要支撑怎样的商业模式，如何进行商业变现，这是支撑其他要素的基础，因此需要首先确定下来。企业开源不可能是做慈善，没有商业变现的支撑，就无法保证持续的投入与发展。业界的开源通常支持以下几种商业模式：软件订阅与支持：售卖围绕开源代码的订阅服务并提供商业支持，如红帽企业 Linux（Red Hat Enterprise Linux，RHEL）、Pivotal Cloud Foundry；特性增强并收费：开源基础版本，但对专有代码的附加组件进行收费，如 GitLab Enterprise 以及大量设备商的产品，包括华为的高斯 DB 和基于 OpenStack、K8S 等开源软件构建的商业软件。关联产品（引流模式）：通过开源软件增加用户触达，并为其他业务导流，例如，安卓开源项目（Android Open Source Project，AOSP）及 Mozilla Firefox项目为 Google 搜索等业务提供导流。软件双许可：一般同一软件会有一个免费许可，具备传染性的 copyleft 开源许可，如 GNU GPL（General Public License），用于吸引广大用户及共建者；另一个则是私有软件许可，收费，但用户可以不受开源许可证（比如 GNU GPL）的限制，并享受商业公司提供的 SLA 保障与服务，如 Linux 桌面系统 Qt。（云）服 务：以 云 服 务 的 方 式 售 卖 开 源 软 件，如 Amazon OpenSearch Service、Google Kubernetes Engine 等；硬件：售卖硬件产品，但将硬件相关软件开源，以吸引并方便开发者使用，例如 Intel Clear Linux 开源项目对 Intel x86 CPU 的支持与使能。华为研究|1042022 年 12 月值得注意的是，开源项目不等于商业产品，哪怕产品的软件源码与开源项目完全一致。商业产品基于开源项目构筑商业模式时需做如下考虑：相对于开源项目，产品要有足够的商业价值；相对于开源项目，产品需要更明确的定位；产品要和开源项目中的软件竞争；不同的公司将使用相同的开源项目软件进行竞争。这里以 RHEL 为例来说明以上几点。RHEL 的所有源码均来自于上游社区RHEL 一直秉承着“上游优先”甚至“上游 Only”的原则，即使是自己开发的特性，也会先合入上游社区再拉取回 RHEL 产品。第一，独特的商业价值。Linux 的服务器操作系统非常复杂，RHEL 通过订阅与支持为客户在使用、管理、配置、维护等方面提供企业级服务，以及丰富的南北向认证，这是开源项目无法提供的独特商业价值。第二，明确的产品定位。RHEL 将企业所关注的操作系统稳定性、长期维护及支持与社区先进特性综合在一起，实现二者之间的均衡，这与上游开源项目本身主要关注新特性开发以及有限版本、较短时长的维护相比，产品定位更加明确，也更贴近企业用户需求。第三，尽管 RHEL 相比上游社区项目具有独特的价值与定位，但难免还是会有用户直接从上游社区项目获取软件，自己集成、安装、维护。RHEL 的做法是与其任由这些用户自由发展，还不如基于 RHEL 版本构建（收购）CentOS 社区，去除所有 RHEL 的商标痕迹，并定期维护、更新 RHEL。用户不仅可以享受到与 RHEL 基本等同的产品质量与维护，而且不用支付任何费用。表面上看，CentOS 似乎与 RHEL 形成了竞争，但实际上它吸引并留存了 RHEL 的潜在客户，也防止了相当数量的用户流向自下载构建操作系统或流向竞争对手。第四，与其他基于相同开源项目的产品竞争。在 Linux商业发行版这个领域内，除了 RHEL，还有 SUSE Linux Enterprise、Ubuntu 等竞品，因此 RHEL 也需要应对来自于这些产品的挑战。这些产品依赖同样的开源项目，因此在特性上大同小异，但在长期竞合中逐渐形成了各自的客户群及生态系统。虽然 RHEL 一家独大，但也能长期共存。2.2 要素二：知识产权策略开源软件拥有完整的知识产权属性，因此一般意义上的公有领域（Public Domain）的智力成果不是开源软件，因为没有与之相关联的知识产权。开源软件知识产权的制定涉及专业的法律问题，因此就如何制定知识产权策略，本文不会提供任何具体的指导。读者可以从如下 4 个维度进行思考，并以此为切入点向知识产权律师或法务专业人员提出诉求，以制定相关策略：开源许可证主动对外开源的开源软件必须选定一个许可证（为适配不同的应用场景或与不同的开源软件集成，有时同一个开源软件也可能选择多个许可证）。一般而言，一旦软件首创者选定了某个开源许可证，后续其他贡献者贡献的代码也自然会采用选定的这个许可证。但有一种情况比较特殊，就是集成发行版。以 openEuler为例，其作为操作系统的发行版，集成了数千款原生上游社区已有的开源软件。这些软件的许可证可能存在差异，因此，许可证是否兼容就决定了这些软件能否集成到一起。考虑到开发者后续可能还会引入新的开源软件以增强操作系统功能，许可证的合规策略一般还会逐单审视、定期刷新。一般集成发行版社区都会采取许可证黑白名单方式，如 Fedora、openEuler社区都有类似机制（https:/fedoraproject.org/wiki/Licensing:Main#Good_Licenses）。此外，开源许可证还存在一些其他挑战，包括：软件中残缺许可证的识别、许可证应用颗粒度的多样性（软件级、模块级、文件级）、许可证场景的多样性（同一许可证在用户态/内核态、静态链接/动态链接等不同场景下的权利和义务也不相同）、软件许可证变更等。这些都需要相关的工具系统（https:/compliance.openeuler.org/）及法律专业人员的深度介入。著作权开源软件不论是托管给开源基金会进行开放治理还是由公司控制治理，著作权所有权（ownership）一般归属于原创开发者或其雇佣者，不会随开源贡献而发生转移。开源只是在许可证或其他类似贡献者协议（CLA 或 DCO）的约束下，赋予使用者（包括开源基金会）非常广泛的著作权权利，比如使用、复制、分发、修改等，有时这些权利甚至是永久的、非排他的、不可召回的（详情可以参考各开源许可证文本及 OSI对于开源软件的定义），但这并不意味着将著作权所有权转移给了其他人。尤其是当原创者或原创企业将开源软件捐赠给开源基金会进行开放治理的时候，这点往往会引起一些误解。这也是各大主流开源基金会所形成的实践（包括但不限于 Linux 基金会、Apache基金会、OpenStack 基金会等）。当然，也有一些开源基金会要求转移著作权，FSF 就是如此（https:/www.gnu.org/licenses/why-assign.en.html），但这更多是出于“软件自由”的理念以及维权便利性的考虑，而非业界（尤其是大企业）主动采用的开源著作权策略。这里要特别指出，即便是在 FSF，这种著作权的转移也不是强制的，只有当贡献者希望由FSF 全权处理维权时才会转移著作权。近来，我们105|华为研究2022 年 12 月软件技术与生态2.3 要素三：开源技术策略2.4 要素四：项目治理与社区平台策略也看到 FSF 旗下的一些项目已经取消了这一策略，例如 GCC 已不再要求转移著作权（https:/news.slashdot.org/story/21/06/05/0246247/gcc-will-no-longer-require-copyrights-be-assigned-to-the-fsf）。专利权 有些许可证有明确的专利免费使用授权，要注意由于开源而丧失专利起诉权利的场景；对于我方重点布局的专利领域，贡献开源及参与开源需要谨慎。最彻底的专利隔离方式是成立独立公司（如高通、爱立信、微软），专职做开源贡献。商标 如果开源项目捐赠给了开源基金会，项目商标的所有权一般也会转移；项目商标与产品商标若存在冲突，在贡献给基金会前要提前准备好新的项目商标；项目商标的使用权，尤其在开放治理的场景下（托管给基金会），一般会对所有使用者一视同仁，无法保留专有权利。开源技术策略分两个维度：技术卖点当前开源项目数不胜数，如何在众多项目中脱颖而出，关键在于技术竞争力及先进性。要解决真实世界的问题：从无到有（O3DE）：在开放 3D 引擎（Open 3D Engine，O3DE）引入之前，市场上主流的商业软件都是闭源的，有限的几款开源引擎要么是 2D 引擎，要么无法提供 AAA 级游戏主机画面质量。AWS 在收购 CryEngine 代码后重新进行改造、增强并开源，希望打破原有产业格局并快速牵引 O3DE 算力上云。从有到优（AOSP）：AOSP 出现之前，基于Linux的移动操作系统有几大痛点，包括但不限于：1）关键组件缺乏高质量的开源软件（如电话子系统 RIL、浏览器、Java 虚拟机等都需要从商业公司购买）；2）各开源组件版本及选型碎片化严重，无法形成统一的应用开发接口，上层应用开发无法归一化，也没有统一的应用市场进行应用分发与变现；3）没有对接新兴的云服务（如地图、搜索服务等）；4）不具备当时代表了下一代操控体验（电容触屏滑动体验）的MMI（iPhone已具备），或需要自己开发或购买第三方组件。而 AOSP 的推出解决了上述所有问题，因此迅速吸引了大量南北向开发者，生态快速成长。巨大愿景（ECOMP）：电信网络云化，见图 3。图 3 电信网络云化的愿景 开什么、闭什么以RHEL为例，基于“上游优先”、“上游Only”原则，RHEL 的代码完全来自上游社区，要如何构筑差异化竞争力呢？因此，RHEL 对如下内容不做开源：构 建 工 具 链，包 括 编 译 选 项（形 成 竞 争 力 1：RHEL 商业版本的二进制优化能力）；打造测试集及相关工具（形成竞争力 2：RHEL商业版本的缺陷解决效率）。项目治理：分为开放治理、封闭治理两种方式，图 4中横轴代表参与者更多是个人导向还是公司导向，以及社区是否接受来自所属公司以外的开发者，与是否由公司控制并无耦合关系 3。代码工程与社区运营平台：包括代码托管及相关的软件工程、运营平台工具（DevOps 流水线、CICD、贡献检查及门禁、开发者门户、官网等），见图 5。图 4 开放治理模型华为研究|1062022 年 12 月有些工具可能存在业务连续性风险，常见的迁移策略包括：商业工具/服务逐步切换成可信供应商；开源组件转国内商业服务；风险开源组件逐渐形成独立维护与演进。图 5 代码工程与社区运营平台2.5 要素五：生态构建策略作为社区的主导者，我们需要引导不同类型的生态伙伴发现参与社区的价值，这里针对 4 种常见类型的生态伙伴分别给出对应的策略 3：用户：通过增加采用量来发展用户生态系统；针对以用户为中心的项目，创建一个完整的发行版；专注于推动下载，集成到其他开源生态系统中去。开发者：通常情况下，最好是将开源项目贡献给开源基金会，以实现开放治理，吸引更多开发者参与进来。专注于框架、平台或工具，而不是完整的发行版，这样有助于提高开发者的生产力；专注于与其他开源开发的轻松整合。其他公司（含友商）：选择现有的基金会，减少他人加入所带来的法务工作。先以项目开发为主，而后建立社区适配，例如：Kubernetes-CNCF，OpenStack-OpenStack 基金会，Ceph-Ceph 基金会，Apache 孵化器-Apache 项目。通 过 优 秀 的 观 众 渠 道 启 动 项 目，例 如，Kubernetes 是 在 2014 年 的 DockerCon 大 会上 启 动 的，而 OpenStack 则 是 在 2010 年 的OSCON 开源大会上启动的。107|华为研究2022 年 12 月软件技术与生态图 6 OpenDayLight 项目的贡献主体示意图2.6 要素六：成功度衡量3 社区构建的度量3.1 社区度量的两个角度 在组建前先宣布组建意向，以招募成员。例如，Linux 基 金 会 曾 于 2015 年 宣 布 其 组 建Hyperledger的意向，但在次年才正式启动组建。与供应商一起招募终端用户，确保项目能提供价值并得到推广。例如，Hyperledger 项目就是与 CME Group、Deutsche Brse、State Street、Wells Fargo 等联手推出的。预先与其他公司沟通并就架构主导与看护达成一致（图 6 以 Cisco OpenDayLight 项目为例）。成员 活动 贡献者 培训 开发者活跃度 下游项目“社区”指的是一群因共同利益而聚集在一起的人或组织。从根本上来说，创建一个成功的社区就是创建一个生态系统，成员们可以在社区中从事有意义的工作，快速提升自我，保持持续成长的动力，这样的社区才能长盛不衰。在确定了项目开源策略之后，就可以对外发布并建立社区了，最终目标是建立一个高成长性、高粘性的可持续发展的开源社区。当然在社区构建和运营过程中，会面临许多问题，例如社区 Issue 长时间无人答复、开发者满意度差、开发者流失等。要解决这些问题，就必须构建一套完善的社区度量体系。社区度量的意义在于衡量社区是否达成了既定的阶段性目标。具体说来，需要制定有效的量化方案，根据度量标准设计合理的预期，及时洞察度量结果以制定改进方案，确保社区健康的发展。一个社区是否成功，可以从两个角度来衡量：一个是开发者角度，一个是社区管理者角度。标准与产业组织 开源的参考实现（EFSP(JCP)-Jakarta EE）开源引领标准化（Docker-OCI）成功度衡量可以从最终商业结果与社区发展过程这两个维度进行。商业结果度量维度相对简单，也是闭环开源策略制定与执行效果的终极度量，但往往需要较长时间才能得出结果，不利于掌握过程并及时进行调整。围绕社区发展过程这个维度，本节主要给出一些常用的中间态结果度量，并指出其对后续商业决策的潜在影响：用户数度量（网站 portal 或用户调查）：用户数或者下载量 社区大小 用户数或者公司数（公司 X 下载了我们项目 200次，所以我们可以尝试将产品卖给它）用户的地理位置（中国区的用户下载量占 30%，所以我们应该在中国区开设一个销售办事处）其他生态活动度量（基金会度量平台或社区洞察 工具）：3.2 面向开发者的度量社区的核心力量是社区成员，而开发者又是社区成员中最关键的角色，高效的开发者是社区成功的关键因素之一。为了建立面向开发者的度量，我们先简要阐述构建成员画像的几个基本原则 6：根据社区的愿景使命及阶段性目标，确定主要成员的画像类型，如用户画像、布道者画像、活动组织者画像、Issue 支持者画像、开发者画像等，有些画像的角色可能是重叠的。由于构建画像需要耗费大量人力，我们应该更关注画像类型的质量而不是数量。在构建成员画像时，需要重点关注以下几个要素：能力、经验、动机、关心的事情、期待的奖励以及关注的领域。下面我们将详细介绍构建开发者画像的过程。华为研究|1082022 年 12 月3.2.1 构建开发者画像3.2.2 建立开发者社区的参与旅程框架开发者画像是用户画像技术在社区开发场景中的一种实践。开发者画像通常由社区开发者的多项特征以及与其他开发者的关联关系构成：开发者特征通常是一系列的标签。如图 7 所示，我们可以通过标签来代表一位开发者在社区中所展现出来的技能特征。图 7 开发者技能云图 8 一名开发者参与贡献的所有项目标签集合图 9 开发者关系图谱开发者关系图谱通常可以分为社交关系、直接协作关系和间接协作关系 4。每种关系下又包含了详细的协作关系，关系类型和关系强度将视为协作关系的属性。在开发者的开发活动中，“社交关系”是指在特定社区中开发者之间的人际关系。虽然与开发活动并不直接相关，但研究发现，开发者加入好友所在的项目，其贡献率将会大幅提升 5。社交关系又可以细分为关注关系和同组织关系，分别表示开发者之间的相互关注和开发者隶属于同一个组织。“直接协作”是指开发者之间存在直接的交互关系，即两个开发者面对同一任务需要紧密的沟通合作。例如开发者 D1 与开发者 D2 之间若存在 Answer to 和 Call API 的关系，则表示 D1 回答了 D2 提出的问题、在实现某些功能时 D1 调用了 D2提供的接口，这些协作的频度用数字表示。此外，开发者共同修改代码文件、对同一代码的开发和测试也属于这种紧密型的协作关系，其他类似的协作关系还有很多，恕不一一列举。最后，“间接协作”是指开发者之间存在间接的交互关系。相对于直接协而言，间接协作是一种较弱的协作关系，但对于整体的开发任务也会起到一定的作用。例如开发者 D1 与开发者D2 都回答了某个问题，或者都向某个开源项目提交了自己的代码，则他们之间就构成了 Co-answer 和 Co-commit 的关系。另外，我们还可以构建开发者的贡献度特征。“贡献度”是指开发者在特定社区中对该社区作出的贡献，主要考察开发者在社区中的活跃度和熟练度。这些贡献覆盖了开发者的各项活动，如在 Gitee 开源社区中参与项目或提交代码，在 Stack Overflow 问答社区中回答问题，等等。如图 8 所示，我们可以构建开发者参与社区的贡献度特征，图中的标签代表该开发者参与的所有项目，圆形直径代表开发者对项目的贡献度，直径越长，贡献度越高。与其他开发者的关联关系可以用开发者关系图谱来表示，通过将开发者之间的交互可视化，来量化社区的协作强度。利用开发者关系图谱，我们可以识别开发者参与社区的趋势特别是核心开发者还可以判断开发者是否有从社区流失的倾向等。如图 9 所示，在完成开发者画像的构建之后，接下来需要建立开发者在社区的参与旅程框架（如图 10 所示），方便度量开发者在不同阶段为社区创造的价值 6。该框架涵盖了社区参与的三个关键部分。不同的成员画像类型，需要不同的参与旅程框架：新人引导：五角星左边代表社区帮助新人以最简单的方式尽快创造价值，价值本身既是新人自己的，也是社区的。109|华为研究2022 年 12 月软件技术与生态3.2.3 构建开发者 NPS 度量模型图 10 开发者社区的参与旅程框架图 11 社区画像成熟度模型图 12 NPS 定义 参与状态转换：五角星右边代表开发者开始在访客 常客 核心成员这三个关键身份之间转换。激励：为了促进社区发展、保持成员的参与度，我们会采取一系列措施（蓝色方块），帮助成员积累经验、培养新技能并维持积极性。在介绍完开发者画像及社区参与旅程框架后，下面我们可以引出社区画像成熟度模型（如图 11 所示），该模型提供了一套工具来定义开发者画像在各阶段的成功：当我们完成了开发者画像的构建，并设计了开发者在整个社区的参与旅程框架，要衡量他们在不同阶段（新人/访客/常客/核心成员）为社区创造的价值，就需要从开发者角度出发构建净推荐度（Net Promoter Score，NPS）度量模型 7通过度量和洞察，让社区与开发者为彼此带来更多价值。NPS 是业界用来衡量用户体验的通用指标，是管理用户体验、提升客户满意度的有效工具。通过一个终极问题你有多大可能会将我们的社区推荐给同事和亲朋好友？为什么?NPS 可以清晰地将用户分成三类，并在此基础上计算出一个简单易懂的值，然后制定出计划，以期改进并获得成功（如图 12 所示）。开发者 NPS 度量模型（图 13）由两部分组成：第一部分是 NPS 度量体系，第二部分是 NPS 反馈体系。通过NPS 度量体系，结合开发者画像，我们可以通过 NPS 问卷调查的形式感知社区存在的问题以及开发者的诉求。通过NPS 反馈体系，及时给出解决方案，调整社区的相关治理机制。最终提升开发者满意度，以及开发者对社区的忠诚度。3.3 面向社区管理者的度量图 13 开发者 NPS 度量模型作为社区的管理者，开源社区有许多度量指标及度量模型可以衡量社区是否成功。但问题是开源项目面临着浩瀚使用方法如下：沿着横轴，可以看到社区参与旅程框架的各个阶段，包括新人、访客、常客和核心成员阶段。针对这些阶段，分别定义各个阶段的成功标准，并利用不同维度的指标来进行度量。个人价值：某成员画像应该为他/她本人带来哪些可度量的价值？例如，对于新人阶段，Issue 支持者画像的成功标准可以定义为“在社区提出新 Issue 并获得答案”。社区价值：某成员画像为社区带来了哪些可度量的价值？例如，对于新人阶段，Issue 支持者画像的成功标准可以定义为“解决了社区其他成员提出的 Issue”。同行价值：某成员画像为社区其他成员带来了哪些可度量的价值？例如，对于常客阶段，成功标准可以是“为社区不同成员提供一对一指导或者培训”。领导力价值：某成员画像在社区领导力方面带来了哪些可度量的价值？华为研究|1102022 年 12 月3.4 社区体验改进3.3.1 选择度量指标3.3.2 核心组织的支持3.4.1 开发者画像助力社区维系开发者图 14 组织能力成熟度模型如烟的数据，任何可以获得数据的对象，都能收集、跟踪。每个组织跟踪的度量标准以及他们如何处理数据在很大程度上取决于自身社区独有的战略目标，以及他们在市场和开源社区中的独特挑战。特别是对于大型组织来说，有太多的项目，不可能跟踪所有的对象并保证此举有意义。为摆脱这一困境，在选择度量指标和度量领域时，需要结合社区的战略目标，投入自己的思考 8。设定社区的战略目标包括：构建社区的远景使命、明确社区为人/组织提供的价值、制定阶段性目标。具体执行过程中，我们需要有针对性地衡量社区的工作成果。在制定具体指标时，我们需要保证目标能够清晰、准确地衡量，切忌模棱两可。为此，我们需要遵循以下四个规则 6：衡量关键维度社区主要有七个关键维度：增长率：有多少新人加入社区？如何随时间变化？留存率：有多少人在持续地参与社区活动？社区内成员的活跃度；组织成员与社区成员的协作活跃度；交付能力：社区内不同的贡献者是否按照其职责提供了相应的价值；出席率：线上、线下活动的出勤情况；高效性：整个社区的运转机制是否畅通无阻？同时度量“质”与“量”跟踪不同类型的贡献数量是衡量活跃度和交付率的好办法，但同时也要验证贡献的质量，做到“质”与“量”兼顾。度量可量化在度量目标是否达成时，我们应能清晰地回答出“是”或“否”，而不是“也许”。限制度量指标的数量我们需要做到精简指标数量，只跟踪关键指标，这样可以保持关注，简化讨论。作为社区的初创者及主导者，核心组织想要真正成功地创建一个社区，需具备从计划、发展、互动到优化社区体验的一整套技能。不仅需要发展这些技能，也需要在组织内部建立支持系统。组织发展这些技能的过程可分为三个阶段 6：1.孵化新技能：营造一个兼具资源、教育、战略和执行力的环境，该环境可以引入新技能、为人员提供培训、在人们应用这些技能时提供支持。2.建立机制：在吸取孵化阶段的经验教训后，需要制定机制、加深团队理解、完善和发展这些标准。3.整合：需要将这些机制推广到组织内所有团队中去。我们将这三个阶段与专业领域的目标技能相结合，构建出了如下组织能力成熟度模型：如图14所示，组织能力成熟度模型从上到下分为七行，每行代表一个专业领域，每个领域皆跨越了技能发展的三个阶段。在使用该模型时，组织需定期复盘，向相关部门收集反馈意见，并将改进计划整合到下一个迭代中去。基于社区健康度度量体系和开发者画像的关系，我们与华东师范大学王伟教授和上海交大曹健教授的团队一起联手，在华为主导的 openEuler/MindSpore 社区实施了社区体验改进。在 OpenEuler 社区中，如图 15 所示，我们通过构建开发者在不同 SIG 组中的技能标签，识别出大多数开发者都参与过 CVE 漏洞的修复工作。对于社区管理者而言，制定更简单的漏洞修复流程、引入自动化漏洞感知和修复工具可以大幅提升开发体验。111|华为研究2022 年 12 月软件技术与生态3.4.2 开发者 NPS 度量模型推动 openEuler社区改进开发者体验图 15 openEuler 开发者标签表 1 开发者旅程图 16 MindSpore 社区协作者关系图谱在 MindSpore 社区中，我们构建了开发者 Issue 交互关系图谱，协助社区管理者识别了 10 不活跃开发者，并通过问卷、线下沟通等方式重新激活了部分存在流失倾向的开发者（如图16所示）。另外，通过构建开发者兴趣图谱，在 MindSpore 社区试点社区安全、前端、数据、科学计算SIG 组，提升了社区的整体活跃度。依据 3.2 节的讨论，现在给出开发者 NPS 度量模型在openEuler 社区的实际应用。如表 1 所示，我们详细定义了开发者通过引新活动（例如meetup）成为社区新人之后可能会经历的所有社区旅程。4 结语当前，越来越多的企业主动拥抱开源，并将开源纳入企业的发展战略。但“为什么开源”、“如何开源”仍是企业不得不面对的实际挑战。从开源策略六要素出发，本文从商业、项目、生态等多个角度全面审视了企业的开源活动，帮助企业通过社区度量掌握开源健康度，构建高成长性、高粘性的开源社区，并最终支撑企业真正实现其开源战略。在每个旅程节点，根据开发者角色（新人/访客/常客/核心成员）构建了不同的开发者画像。然后引入 NPS 调查问卷，对这些画像精准投放不同的问题，以获得开发者明确、清晰的反馈。通过这种方式，帮助社区及时发现问题，做针对性的管理与改进，最终提升开发者对社区的忠诚度。华为研究|1122022 年 12 月参考文献1 Raymond and Eric S(1999),The cathedral and the bazaar:Musings on Linux and open source by an accidental revolutionary,OReilly Media.ISBN 1-56592-724-9.2 Richard Stallman,FLOSS and FOSS,Accessed 9 October 2022.3 Bryan Che,OpenSource policy4 张建，孟祥鑫，孙海龙，王旭，刘旭东,数据驱动的软件开发者智能协作技术,大数据,202101:76-93,2021.5 杨程，范强，王涛，尹刚，王怀民,基于多维特征的开源项目个性化推荐方法,软件学报,2017,28(6):1357-1372,20176 Jono Bacon(2019),People powered,HarperCollins Focus.ISBN 9781400214884.7 Fred Reichheld and Rob Markel,The ultimate question 2.0(revised and expanded edition):How net promoter companies thrive in a customer-driven world,20118 Christine Abernathy,Chris Aniszczyk,Joe Beda,Sarah Novotny,and Gil Yehuda,Measuring your open source programs success,Accessed 9 October 2022.113|华为研究2022 年 12 月软件技术与生态全球导航卫星系统动态实时差分（Global Navigation Satellite System Real-Time Kinematic，GNSS-RTK）定位可以基于固定解实现高精度定位，是自动驾驶车辆（Autonomous Driving Vehicles，ADV）绝对定位的必备技术。但城市建筑物对信号的阻挡、反射和衍射会使 GNSS-RTK 定位的性能大幅下降。因此，本文提出一种新方法，利用 3D LiDAR 和惯性传感器生成局部环境映射，排除 GNSS 潜在非视距（Non-Line-of-Sight，NLOS）接收信号，进一步提升城市峡谷场景下 GNSS-RTK 定位的性能。首先，通过基于因子图优化的 LiDAR/惯性积分构建局部环境描述，即 3D点云图（Point Cloud Map，PCM）。然后，在 GNSS-RTK 定位前采用 3D PCM 检测并排除 GNSS 潜在 NLOS 接收信号。最后采用优化后的 GNSS-RTK 定位校正 LiDAR/惯性积分构建的 3D PCM 所产生的漂移。实验利用低成本车载GNSS 接收机在不利于定位的城市环境中采集测试数据集，验证了该方法的有效性。摘要Han Gao1，Weisong Wen2，Li-Ta Hsu2，Yongliang Wang11黎曼实验室 2香港理工大学航空及民航工程学系智能汽车 LiDAR 辅助 GNSS-RTK 定位关键词GNSS，RTK，NLOS，LiDAR，城市峡谷华为研究|1142022 年 12 月1 引言全球导航卫星系统动态实时差分（Global Navigation Satellite System Real-Time Kinematic，GNSS-RTK）广泛应用于高精度航空测绘 1 以及 L4 等级的全自动驾驶车辆（Autonomous Driving Vehicle，ADV）定位2。GNSS-RTK 定位通常包括两个步骤：（1）根据接收的 GNSS 测量数据估计浮点解。（2）基于估计的浮点解，采用最小二乘算法（如 LAMBDA 3）计算整周模糊度，并作为初始猜测值。通过双差分载波和码测量可以在露天区域基于固定解实现厘米级定位。但在城市峡谷场景中，周边建筑物对 GNSS 信号的反射和阻挡会产生 NLOS 和多径接收信号，使 GNSS-RTK 定位的精度大幅下降。问题的根本原因是 GNSS NLOS 接收信号。因为部分 GNSS接收信号被严重污染，产生大量噪声。根据以往研究 4，高度城市化地区中大部分 GNSS 接收信号都是多径信号或NLOS 信号。因此，基于差分载波和码测量估计的浮点解，其精度有所下降，模糊度更难求解。近几十年，57 开展了大量研究以提升城市峡谷场景下 GNSS-RTK 定位的性能。6 提出采用多天线提升GNSS-RTK 离群值测量的鲁棒性，但该方法的有效性取决于 GNSS 污染信号量（多径信号或 NLOS 接收信号量）。最近，5 提出通过 3D 建筑模型来排除 GNSS 污染信号，以提升城市峡谷场景下 GNSS-RTK 定位的性能。该方法可以通过视距（Line-of-Sight，LOS）测量提高固定率，但需要精确的 3D 建筑模型和 GNSS 接收机位置的初始猜测值。另一个研究方向是通过传感器融合来增加传感器。GNSS-RTK 和 惯 性 测 量 单 元（Inertial Measurement Unit，IMU）的结合能够带来更多增益，因此已被广泛研究。根据 8，在信号较好的典型城市场景中，高级双频多GNSS-RTK 定位在 1 小时车程内的正确整周模糊度固定率可达 76.7%。但总体定位性能很大程度上取决于 GNSS中断期间 IMU 传感器的成本 9。10 和 11 提出了在不利于 GNSS 定位的环境中将 GNSS-RTK 与视觉测量紧密结合，以提升定位性能。但是，视觉测量对动态对象的照明条件和密度比较敏感，而且视觉测量的比例复原在很大程度上取决于 GNSS 测量数据的质量。4，1315 没有采用视觉测量，而是提出通过 3D LiDAR 传感器不断提升城市峡谷场景下 GNSS 单点定位（Single Point Positioning，SPP）的性能，因为 3D LiDAR 传感器鲁棒性较高，且不受照明条件影响。该方法利用 3D LiDAR 传感器生成的3D 点云来描述周边环境，进一步排除 4 或校正 GNSS NLOS 接 收 信 号 13。16 的 最 新 成 果 结 合 了 GNSS NLOS接收信号的校正与重构，通过增量构建环境描述（3D PCM）提升城市场景下 GNSS SPP 定位的性能。但该方法只采用了码测量，没有对载波相位测量进行探讨。本文基于 4 和 13 的 3D LiDAR 辅助 GNSS SPP定位，提出通过 3D LiDAR 传感器从根本上解决信号反射和阻挡引起的定位精度下降问题，从而提升城市峡谷场景下GNSS-RTK 定位的性能。首先，根据 17 的最新成果，通过因子图优化（Factor Graph Optimization，FGO）将 LiDAR 和 IMU 测量松散结合，实现 LiDAR/惯性里程计（LiDAR/Inertial Odometry，LIO），以估计两个历元间的相对运动，并生成 3D PCM（即局部环境描述）。再基于 16，利用 PCM 检测和排除 GNSS 潜在 NLOS 接收信号，从而提升 GNSS 测量数据的质量。然后利用未排除的 GNSS 卫星测量信号估计浮点解，并采用 LAMBDA算法求解模糊度。最后，结合 GNSS-RTK 定位固定解的估计值和 LIO，进一步校正 3D 点云漂移。简而言之，该方法有效结合了 LIO 和 GNSS-RTK 定位。LIO 在短周期内局部精度高，并为GNSS NLOS信号检测提供了环境描述。GNSS-RTK 定位提供了无漂移的全局参考位置，但结果受 GNSS NLOS 接受信号的影响。本文的研究成果如下：（1）通 过 LiDAR/惯 性 积 分 检 测 和 排 除 GNSS 潜 在NLOS 接收信号，进一步提升 GNSS-RTK 定位的性能。这是 LiDAR/惯性积分被首次应用于排除此类信号。（2）通过优化后的 GNSS-RTK 定位校正 3D 点云漂移，提高整体定位精度。（3）利用低成本 GNSS 接收机采集的数据集来评估该方法的有效性。以下是本文各部分简介。第 2 节提供方法概述。第 3节介绍如何生成局部环境描述。第 4 节介绍 NLOS 信号检测和 GNSS-RTK 定位。第 5 节采用香港城市峡谷场景中采集的数据集进行实验，评估方法的有效性。第 6 节得出结论，并提出未来研究方向。2 方法概述方法概述如图 1 所示，由两部分组成：（1）基于 3D LiDAR 和 IMU 在云上生成实时环境描述，并校正 GNSS-RTK 解。（2）基于实时环境描述检测和排除 GNSS NLOS 信号，并基于未排除的卫星信号进行 GNSS-RTK定位。本文用加粗大写字母表示矩阵，用加粗小写字母表示向量，用斜体小写字母表示可变标量，用小写字母表示常量标量。GNSS 接收机状态和卫星位置均采用东北天坐标系（East,North,Up，ENU）表示。为使描述更加清晰，本文定义了以下几种符号：给定历元k内卫星s接收的伪距测量值为sr,k。下标r表示 GNSS 接收机，k表示时间索引，上标s表示卫星索引。给定历元k内卫星s接收的载波相位测量值为sr,k。地心地固坐标系（Earth-centered,Earth-fixed，115|华为研究2022 年 12 月软件技术与生态ECEF）或 ENU 坐标系中的变量用上标 G 和下标 L表示。例如，在 ENU 坐标系和 ECEF 坐标系中，位姿和位置的转换为TGL=RGL,tGL，其中RGL和tGL分别表示旋转和平移。AHRS、LiDAR 和 GNSS 接收机的体坐标系用上标BI、BL 和 BR 表示。例如，PBLk表示历元k内的一个3D LiDAR 点云坐标系。GNSS 接 收 机 和 3D LiDAR 之 间 的 外 部 参 数 为TBRBL=RBRBL,tBRBL。IMU 和 3D LiDAR 之间的外部参数为TBIBL=RBIBL,tBIBL。ECEF 坐 标 系 中，卫 星s在 给 定 历 元k的 位 置 为sk=sk,x,sk,y,sk,zT。ECEF 坐标系和 ENU 坐标系中，GNSS 接收机在给定 历 元k的 位 置 为pGr,k=pGr,k,x,pGr,k,y,pGr,k,zT和pLr,k,x,pLr,k,y,pLr,k,zT。ENU 坐 标 系 的 旋 转 为RLr,k=Lr,k,x,Lr,k,y,Lr,k,zT。GNSS 接收机在给定历元k的钟差为r,k，单位为米。sr,k表示卫星钟差，单位为米。云云LiDAR扫描匹配LiDAR因子LiDAR因子局部FGOPCM校正位置估算值位置估算值预积分PCMPCMPCMPCMGNSS NLOS信号排除GNSS-RTK浮点解估算浮点解位置估算值浮点解位置估算值浮点解GNSS接收机载波伪距测量GNSS接收机载波伪距测量最小二乘法定位卫星测量数据卫星测量数据模糊度求解模糊度固定解模糊度固定解加速度计和陀螺仪加速度计和陀螺仪卫星测量数据IMU因子卫星测量数据IMU因子图 1 方法概述。输入为 IMU、3D LiDAR 和 GNSS 接收机的原始测量数据，输出为 GNSS 接收机的估计状态。3 生成局部环境描述本节介绍如何基于 LiDAR/惯性传感器生成局部环境描述，以及如何进行 GNSS-RTK 校正。首先，采用LiDAR/惯性积分通过局部 FGO 生成 3D PCM（如图 1 所示）。然后利用 3D PCM 检测 GNSS NLOS 接收信号。但是 LiDAR/惯性积分会随着时间的推移产生漂移。3D PCM 漂移可以通过全局 FGO 结合 GNSS-RTK 和 LIO，利用优化后的 GNSS-RTK 定位结果进行校正（如图 1 所示）。PCM 采用 ENU 坐标系表示，ENU 坐标系和原始LiDAR 坐标系之间的外部参数通过前几个 GNSS-RTK 固定解进行校正 18。3.1 基于局部 FGO 的 LiDAR/惯性积分3.1.1 IMU 预积分模型LiDAR/惯性积分是 17 最近发表的研究（该文献探讨了基于滑窗的 FGO 松耦合积分），并非本文的主要研究成果。但为了论述的完整性，本节提供了 LiDAR/惯性积分的简介。世界坐标系中第k个 IMU 状态，即捕捉到 LiDAR点云第k个坐标系时的 IMU 状态可表示为：xBL(0)k=?pBL(0)BIk,vBL(0)BIk,qBL(0)BIk,bak,bgk?(1)(1)其中，xBL(0)k包括位置、速度、四元数旋转、加速度偏差bak和陀螺仪偏差bgk。因此，FGO 局部窗口内的状态集（XBL(0)）可表示为：XBL(0)=?xBL(0)0,xBL(0)1,xBL(0)K?(1)(2)其中，K表示 FGO 滑窗的大小。IMU 单元用于测量 IMU 体坐标系中系统的角速度和比力。加性噪声以及加速度和陀螺仪偏差缓变会使测量结果产生偏差 19：aBI=RBIBL(0)(aBL(0)gBL(0) ba na(3)(4)BI=BI bg ng(1)aBI是 IMU 体坐标系的原始 IMU 加速度测量值，aBL(0)是 ENU 坐标系中系统的无噪加速度。gBL(0)是世界坐标系中的重力。RBIBL(0)SO3是从 ENU 坐标系到 IMU体坐标系的旋转矩阵。ba表示加速度偏差缓变，其导数服从高斯分布。na N(0,2a)是加速度的加性噪声。BI是IMU 体坐标系中的原始 IMU 陀螺仪测量值，BI是无噪旋转速率。bg是BI的偏差，同样假设其导数对象服从高斯分布。ng N(0,2g)是BI的加性噪声。考虑到 IMU 测量的高频特性，采用 IMU 预积分技术将多个 IMU 测量值堆叠到单个因子中 19，则局部坐标系Bk中的 IMU 预积分公式为：BIkBIk 1=?tk 1tkqBIkBIt(aBIt bak)t2(5)华为研究|1162022 年 12 月3.2 LIO 与基于全局 FGO 的 GNSS-RTK积分3.1.2 LiDAR 扫描匹配测量模型3.1.3 求解局部 FGOBIkBIk 1=?tk 1tkqBIkBIt(aBIt bak)t(6)qBIkBIk 1=?tk 1tkqBIkBIt?012(BIt bgk)?t(7)其中，BIkBIk 1、BIkBIk 1和qBIkBIk 1分别是位置、速度和旋转的预积分。实际上，IMU 测量是离散的，并通过线性插值与 LiDAR 坐标系同步。本文不采用上述的连续数值积分，而是采用中位积分。假设BIt和BIt 1是两个历元BIk和BIk 1之间的两个连续时间点，t是BIt和BIt 1之间的时间间隔。中位积分作为两个 IMU 状态间的相对运动测量值，可以起到约束作用。残差rIMU(zBIkBIk 1,XBL(0)可定义为 19：rIMU(zBIkBIk 1,XBL(0)=(qBL(0)BIk)1(pBL(0)BIk 1 pBL(0)BIk vBL(0)BIkt 12gBL(0)t2)BIkBIk 12?(qBIkBIk 1)1(qBL(0)BIk)1 qBL(0)BIk 1)?xyz(qBL(0)BIk)1(vBL(0)BIk 1 vBL(0)BIk gBL(0)t)BIkBIk 1bak 1 bakbgk 1 bgk(1)(8)其中，运算符xyz用于提取四元数的虚部。zBIkBIk 1表示预积分测量值，由BIkBIk 1、BIkBIk 1和qBIkBIk 1组成。本节采用 20 提出的扫描匹配法推导 3D 点云连续坐标系之间的相对运动。对这些相对运动进行累加，则LiDAR 里程计在给定历元k的位姿估计值为TBL(0)BLk，计算公式如下 17：TBL(0)BLk=?pBL(0)BLk,qBL(0)BLk?(1)(9)LiDAR 扫描匹配的残差rL(TWLk,X)可表示为TBL(0)BLk和xBL(0)k之间的差值：rL(TBL(0)BLk,XBL(0)=pBL(0)BLk pBL(0)BLk2?(qBL(0)BLk)1 qBL(0)BLk?xyz(1)(10)17 介绍了扫描匹配的详细推导过程。根据残差推导结果，可通过以下组合目标函数优化滑窗内的状态集XBL(0)21：XBL(0)=arg min12K?k=0(?rL(TBL(0)BLk,XBL(0)?2CLk) K1?k=0(?rIMU(zBIkBIk 1,XBL(0)?2CBIkBIk 1)(11)其中，rL(TBL(0)BLk,XBL(0)表示 LiDAR 扫描匹配因子的残差，zBIkBIk 1和rIMU(zBIkBIk 1,XBL(0)分别表示 IMU预积分因子的测量值和残差，XBL(0)是待估计的最优状态。CLk表示基于 17 推导的 LiDAR 扫描匹配因子的协方差矩阵。CBIkBIk 1表示 IMU 预积分因子的协方差矩阵。()表示基于柯西核 22 的鲁棒性损失函数。最后，采用 Ceres Solver23 求 解 这 个 非 线 性 问 题，通 过 Levenberg-Marquardt（L-M）算法 24 迭代最小化代价函数（11）。基于状态集XBL(0)，在局部 FGO 滑窗内累加原始 3D 点云可以生成 PCM，结果表示为MBL(0)k。全局 FGO 是 LIO 位姿估计（见 3.1 节）和 GNSS-RTK 定位的融合。与 LIO 类似，全局 FGO 优化了滑窗内的状态集。ENU 坐标系中 IMU 坐标系的第k个状态可表示为：xLk=?pLBIk,qLBIk?,(1)(12)其中，xLk由 ENU 坐标系中的位置和四元数旋转组成。FGO 局部滑窗内的状态集(XLk)可表示为：XL=?xL0,xL1,xLK?,(1)(13)(14)(15)(16)其 中，K表 示 FGO 滑 窗 的 大 小。假 设 优 化 后 的GNSS-RTK 位姿估计公式如下：zGr,k=?pGr,k,x,pGr,k,y,pGr,k,z?T(1)其中，zGr,k用 ECEF 坐标系表示。则zGr,k的残差为：rGNSS(zGr,k,XL)=?(TGL)1(zGr,k tGL)pLBIk?(1)其中，rGNSS(zGr,k,XL)表示与zGr,k关联的残差。根据LIO，给定历元k的观测结果是xBL(0)k，给定历元k 1的观测结果是xBL(0)k1。残差计算公式如下：rLIO(xBL(0)k1,xBL(0)k,xLk1,xLk)=(P1 P2)(pLBIk pLBIk1)2?(R2)1R1)(pLBIk1 pLBIk)?xyz(1)117|华为研究2022 年 12 月软件技术与生态其中：P1=(pLBL(0)1(RBIBL)1(pBL(0)BLk tBIBL)tLBL(0)P2=(pLBL(0)1(RBIBL)1(pBL(0)BLk1 tBIBL)tLBL(0)R1=(qLBL(0)1qBL(0)BLk(RBIBL)1R2=(qLBL(0)1qBL(0)BLk1(RBIBL)1(17)(18)(19)(20)(21)(22)为使推导过程更加清晰，本文定义了P1和P2。根据残差推导结果，可通过以下组合目标函数优化滑窗内的状态集XL21：XL=arg min12K?k=0(?rGNSS(zGr,k,XL)?2CGNSS) K1?k=0(?(xBL(0)k1,xBL(0)k,xLk1,xLk)?2CLIO)其 中，rGNSS(zGr,k,XL)表 示 GNSS 因 子 的 残 差，rLIO(xBL(0)k1,xBL(0)k,xLk1,xLk)表示 LIO 因子的残差，XL是待估计的最优状态。CGNSS表示 GNSS 因子的协方差矩阵。CLIO表示 LIO 因子的协方差矩阵。与局部 FGO 类似，通过 Ceres Solver23 利用 L-M 算法 24 求解公式(18)。基于状态集XL，在全局 FGO 滑窗内累加原始 3D 点云可以校正 PCM，表示为MLk。与 16 相比，通过 GNSS-RTK 定位积分生成的 PCM 没有漂移，这是本文的研究成果之一。4 NLOS 信号排除与 GNSS-RTK定位4.1 基于 PCM 的 GNSS NLOS 信号排除4.2 基于未排除卫星的 GNSS-RTK 定位GNSS 接收机sr,k的伪距测量值可表示为 25：sr,k=rsr,k c(r,k sr,k) Isr,k Tsr,k sr,k(1)其中，rsr,k是卫星和 GNSS 接收机之间的几何范围。Isr,k表示电离层延迟距离，Tsr,k表示对流层延迟距离。sr,k表示多径效应、NLOS 接收信号、接收机噪声和天线相位相 关 噪 声 引 起 的 误 差。大 气 效 应（Tsr,k和Isr,k）通 过RTKLIB 的传统模型（Saastamoinen 和 Klobuchar 模型）进行补偿 26。由于 ENU 坐标系中的 PCM、卫星仰角和方位角可以基于伪距测量值通过最小二乘法计算，因此可以通过 16 提出的快速搜索方法检测 GNSS NLOS 接收信号。GNSS NLOS 接收信号检测如图 2 所示。假设历元k内接收的卫星集为SVr,k=SV1r,k,SVir,k,SVNr,k，其中包括 LOS 和NLOS 卫星。变量N表示历元k内接收的卫星数量。SVir,k表示卫星i的测量值。检测和排除 GNSS NLOS 接收信号后，未排除的卫星集为SSVr,k=SV1r,k,SVir,k,SVMr,k，其中变量M表示未排除的卫星数量。图 2 基于 PCM 检测 NLOS 接收信号。红圈表示 GNSS NLOS卫星，蓝圈表示 LOS 测量数据，圈内数字表示卫星仰角。GNSS 接收机的每次载波相位测量sr,k表示为 25：sr,k=rsr,k c(r,k sr,k) Isr,k Tsr,k Bsr,k sr,k sr,k(1)变量表示载波波长。变量sr,k表示载波相位校正项，其中包括天线相位偏移和变化、固体潮引起的站位移、相位转绕效应和卫星时钟相对论性校正。sr,k表示多径效应、NLOS 接收信号、接收机噪声和天线时延引起的误差。Bsr,k是载波相位偏差，其计算公式如下。26 介绍了载波相位校正的详细公式。Bsr,k=r,0,k s0,k Nsr,k(1)变量r,0,k表示接收机本振的初始相位。类似地，变量s0,k代表卫星发射的导航信号的初始相位。变量Nsr,k表示载波相位的整周模糊度。卫星s的双差（Double Difference，DD）伪距测量（sDD,k）公式如下：sDD,k=(sr,k sb,k)(wr,k wb,k)(1)变量wb,k和sb,k代表参考站接收的伪距测量值，参考站用下标 b 表示。仰角最高的卫星其多径和 NLOS 误差往往最小。因此以仰角最高的卫星w为主卫星。将 DD 应用于伪距测量后，推导出来的sDD,k没有钟差，且不受大气效应的影响 26。类似地，卫星s的 DD 载波相位测量（sDD,k）公式如下：华为研究|1182022 年 12 月(23)(24)(25)(26)(27)(28)(29)(30)(31)5 实验结果及相关讨论5.1 实验设置sDD,k=(sr,k sb,k)(wr,k wb,k)(1)变量sb,k和wb,k代表参考站接收的载波相位测量值。同样，sDD,k也没有括钟差，且不受大气效应的影响。变量sDD,k包括待估计的 DD 模糊度 26。GNSS-RTK 的浮点解可表示为：xfloatr,k=(pGr,k,N1rb,k,N2rb,k,NM1rb,k)T其中，变量xfloatr,k表示 GNSS 接收机在历元k内的状态，该状态由 ECEF 坐标系中的位置（pGr,k）和 DD 模糊度组成。变量NM1rb,k表示卫星M 1的 DD 载波相位模糊度偏差。换句话说，每个 DD 载波相位测量值都有特定的模糊度偏差。因此，DD 伪距测量的观测模型（sDD,k）可表示为：sDD,k=hsDD,k(xr,k,psk,pwk,pb) sDD,k(1)hsDD,k(xr,k,psk,pwk,pb)=(?xr,k psk?pb psk?)(?xr,k pwk?pb pwk?)(1)变 量sDD,k表 示 与sDD,k关 联 的 噪 音。函 数hsDD,k()表 示 计 算 GNSS 接 收 机 状 态 和 DD 测 量 值sDD,k的观测函数。DD 伪距测量的误差因子如下：?esDD,k?2sDD,k=?sDD,k hsDD,k(xr,k,psk,pwk,pb)?2sDD,k(1)变量sDD,k表示与变量sDD,k关联的协方差，该变量通过收到的卫星测量信号的仰角和信噪比（Signal-to-Noise Ratio，SNR）计算得出。同样，DD 载波相位测量的观测模型可表示为：sDD,k=hsDD,k(xr,k,psk,pwk,pb) sDD,k(1)hsDD,k(xr,k,psk,pwk,pb)=(?xr,k psk?pb psk?)(?xr,k pwk?pb pwk?) Nsrb,k(1)变量sDD,k表示与sDD,k关联的噪声。变量Nsrb,k表示载波相位测量的 DD 模糊度。则 DD 载波相位伪距测量的误差因子如下：?esDD,k?2sDD,k=?sDD,k hsDD,k(xr,k,psk,pwk,pb)?2sDD,k(1)变 量sDD,k代 表 与sDD,k关 联 的 协 方 差。则GNSS-RTK 浮点解估计的目标函数为：xfloatr,k=arg min?s,k(?esDD,k?2sDD,k ?esDD,k?2sDD,k)(1)变量xfloatr,k表示浮点解的最优估计值。通过 Ceres Solver 23 求解上述目标函数（31），可得出当前历元的GNSS-RTK 浮点解。得到 GNSS-RTK 浮点解后，使用模糊度求解算法估计固定解。载波相位测量值没有噪声时，变量Nsr,k应为整数。本文通过广泛应用的 LAMBDA 算法 28 求解整周模糊度，得到固定解xfixr,k。然后将固定解代入全局 FGO 来校正 3.2 节中的 PCM 漂移。本节通过香港典型城市场景中采集的数据集验证本文方法的有效性。实验采用多传感器数据采集车，如图 3 所示。测试场景如图 3 右下角所示，街道两侧有高楼和树木，不利于 GNSS-RTK 定位。实 验 采 用 u-blox M8T GNSS 接 收 机 以 1Hz 的 频率采集 GPS/北斗的原始测量数据，并部署了一个 3D LiDAR 传感器（Velodyne 32）以 10 Hz 的频率采集原始3D 点云数据，同时采用 Xsens Ti-10 IMU 以 200 Hz 的频率收集数据。此外，还采用了 NovAtel SPAN-CPT 提供地面真值，这是一个 GNSS（GPS、GLONASS 和北斗）RTK/INS（光纤陀螺仪、FOG）组合导航系统。FOG陀螺仪偏差运行稳定性为 1 度/小时，随机游动为 0.067度/小时。数据采集车与 GNSS 基站间的基线距离约为 5公里。所有数据均采用机器人操作系统（Robot Operation System，ROS）29 来收集和同步。实验前已对所有传感器间的坐标系统进行校正。u-blox接收机IMU传感器3D LiDARSPAN-CPT图 3 数据采集车和测试场景119|华为研究2022 年 12 月软件技术与生态下面通过比较三种方法分析 GNSS-RTK 定位性能，验证本文方法用于提升 GNSS-RTK 定位性能的有效性。分析采用ENU坐标系评估精度，以第一个点作为参考位置。（a）GNSS-RTK：基于 u-blox M8T 接收机原始测量数据的传统 GNSS-RTK 定位方案 26。模糊度逐历元求解。（b）u-blox 接收机:基于 u-blox M8T 接收机、无参考站校正的商用 GNSS 定位方案（c）GNSS-RTK-C：基 于 u-blox M8T 接 收 机 的 原始测量数据以及本文 GNSS NLOS 信号排除法的GNSS-RTK 定位方案。模糊度逐历元求解。以上三种方法的结果对比如表 1 所示。表格第一行是用于定位估计的卫星数量。GNSS 定位平均需要 17 颗卫星的接收信号，而本文的 GNSS NLOS 信号排除法平均只需要 15.8 颗卫星的接收信号。第二列为 u-blox 接收机的2D 定位误差，定位结果基于 u-blox 接收机的标准 NMEA消息。平均误差为 6.25 米，标准差为 7.31 米，最大误差为 38.53 米。整个过程都采用了 GNSS 方案。第三列为传统 GNSS-RTK 定位的结果。u-blox 接收机和参考站的原始测量数据使平均误差降低到 2.43 米，标准偏差和最大误差分别下降到 1.16 米和 7.20 米。由于测量数据的质量问题，固定率只有 1.0%。本文的 GNSS NLOS 信号排除法（GNSS-RTK-C）使平均误差降至 1.95 米，标准偏差为1.003米，但最大误差为12.40米，与GNSS-RTK的7.20米相比大幅增加。不过固定率小幅度上升至 1.6%。实验结果证明，本文方法能够有效减少NLOS信号对定位的影响。5.2 城市峡谷场景性能评估150100500-50050100150200轨迹地面真值GNSS-RTKu-blox接收机GNSS-RTK-C树木东（米）北（米）图 4 三种方法的轨迹。黑色曲线表示地面真值，红色、绿色和蓝色曲线分别表示 GNSS-RTK、u-blox 接收机和 GNSS-RTK-C 方案。表 1 定位性能对比图 5 上方为三种方法的误差。红色、绿色和蓝色曲线分别表示 GNSS-RTK、u-blox 接收机和 GNSS-RTK-C方案。下方为排除的 GNSS NLOS 卫星数量。时间（秒）误差误差（米）NLOS卫星数时间（秒）NLOS卫星数1510505.4995.49955.55.50055.5015.50155.5025.502543215.4995.49955.55.50055.5015.50155.5025.5025GNSS-RTKu-blox接收机GNSS-RTK-C上述三种方法的轨迹以及地面真值如图 4 所示，整个实验的定位误差如图5所示。在图5圆圈标出的历元A附近，本文方法引起的定位误差明显大于传统的 GNSS-RTK，其原因是过度排除 GNSS NLOS 信号。图 4 中部为接近历元 A 的场景，其中树木较多。图 5 下方为排除的卫星数量，采用生成的 PCM 检测到其中四颗卫星属于 NLOS 卫星。排除 NLOS 卫星后，卫星的几何分布严重扭曲，导致定位误差增加。4、30 和 31 也发现了类似现象。总体而言，本文方法（GNSS-RTK-C）与传统方法（GNSS-RTK）相比，能够有效检测和排除 GNSS 潜在NLOS 信号，从而提高定位性能。但两种方法的固定率都不高（GNSS-RTK：1.0%，GNSS-RTK-C：1.6%），对于 GNSS-RTK-C 而言，这主要是因为排除 GNSS NLOS 信号会使卫星的几何分布变差。项目u-blox 接收机GNSS-RTKGNSS-RTK-C平均卫星数171715.8平均误差6.25 米2.43 米1.95 米标准差7.31 米1.16 米1.003 米最大误差38.53 米7.20 米12.40 米固定率不涉及1.0%1.6%华为研究|1202022 年 12 月6 结语GNSS-RTK 定位目前仍然是实现自动驾驶定位的必备技术，自动驾驶需要精确的绝对定位。但是由于信号反射和卫星几何分布较差，GNSS-RTK 定位难以广泛应用于城市峡谷场景。本文提出一种新方法，通过车载传感（LiDAR/惯性积分）检测和排除 GNSS 潜在 NLOS 信号，从而提升 GNSS-RTK 定位的性能。对于实验数据集，本文的NLOS 信号排除法使 GNSS-RTK 定位的精度从 2.43 米提高到 1.95 米。但由于排除 GNSS NLOS 信号会使卫星的几何分布变差，因此 GNSS-RTK 固定率仍然较低。未来，更多的环境特征将作为伪卫星被用于优化卫星的几何分布，进一步提高城市峡谷场景下GNSS-RTK定位的整周模糊度固定率。多个 3D LiDAR 也将被用于生成更全面、更详细的 PCM，从而增大环境重构的视场角。1 P.J.Teunissen and A.Kleusberg,GPS for geodesy,Springer Science&Business Media,2012.2 G.Wan et al.,Robust and precise vehicle localization based on multi-sensor fusion in diverse city scenes,in 2018 IEEE International Conference on Robotics and Automation(ICRA),2018:IEEE,pp.4670-4677.3 P.J.Teunissen,Least-squares estimation of the integer GPS ambiguities,in Invited lecture,section IV theory and methodology,IAG general meeting,Beijing,China,1993.4 W.Wen,G.Zhang,and L.T.Hsu,Correcting NLOS by 3D LiDAR and building height to improve GNSS single point positioning,Navigation,vol.66,no.4,pp.705-718,2019.5 R.Furukawa,N.Kubo,and A.El-Mowafy,Prediction of RTK-GNSS performance in urban environments using a 3D model and continuous LOS method,in Proceedings of the 2020 International Technical Meeting of The Institute of Navigation,2020,pp.763-771.6 P.Fan,W.Li,X.Cui,and M.Lu,Precise and robust RTK-GNSS positioning in urban environments with dual-antenna configuration,Sensors,vol.19,no.16,p.3586,2019.7 T.Li,H.Zhang,Z.Gao,Q.Chen,and X.Niu,High-accuracy positioning in urban environments using single-frequency multi-GNSS RTK/MEMS-IMU integration,Remote Sensing,vol.10,no.2,p.205,2018.8 G.C.Chung,S.T.Su,and M.Y.Alias,Adaptive windowed statistical selection rake for long ultra-wideband multipath channels,(in English),Wireless Pers Commun,vol.98,no.1,pp.453-466,Jan 2018,doi:10.1007/s11277-017-4878-8.9 H.T.Zhang,Performance comparison of kinematic GPS integrated with different tactical grade IMUs,CALGARY,ALBERTA:THE UNIVERSITY OF CALGARY,2006.10 P.Henkel,A.Blum,and C.Gnther,Precise RTK positioning with GNSS,INS,Barometer and Vision,参考文献121|华为研究2022 年 12 月软件技术与生态in Proceedings of the 30th International Technical Meeting of the Satellite Division of The Institute of Navigation(ION GNSS 2017),2017,pp.2290-2303.11 T.Li,H.Zhang,Z.Gao,X.Niu,and N.El-Sheimy,Tight fusion of a monocular camera,MEMS-IMU,and single-frequency multi-GNSS RTK for precise navigation in GNSS-challenged environments,Remote Sensing,vol.11,no.6,p.610,2019.12 X.Bai,W.Wen,and L.-T.Hsu,Performance analysis of visual/inertial integrated positioning in typical urban scenarios of Hong Kong,in Proceedings of 2019 Asian-Pacific Conference on Aerospace Technology and Science,2019.13 W.Wen,G.Zhang,and L.-T.Hsu,GNSS NLOS exclusion based on dynamic object detection using LiDAR point cloud,IEEE Transactions on Intelligent Transportation Systems,2019.14 G.Zhang,Weisong Wen,and L.-T.Hsu,Correcting GNSS NLOS by 3D LiDAR and building height,ION GNSS 2018,Miami,Florida,USA,2018.15 W.Wen,G.Zhang,and L.-T.Hsu,Exclusion of GNSS NLOS receptions caused by dynamic objects in heavy traffic urban scenarios using real-time 3D point cloud:An approach without 3D maps,in Position,Location and Navigation Symposium(PLANS),2018 IEEE/ION,2018:IEEE,pp.158-165.16 W.Wen,3D LiDAR aided GNSS and its tightly coupled integration with INS via factor graph optimization,in Proceedings of the 33rd International Technical Meeting of the Satellite Division of The Institute of Navigation(ION GNSS 2020),2020,pp.1649-1672.17 J.Zhang,W.Wen,F.Huang,and L.-T.Hsu,Loosely coupled Lidar-inertial odometry for urban positioning and mapping(to be submitted),Remote Sensing,2021.18 W.Wen,G.Zhang,and L.-T.Hsu,Object-detection-aided GNSS and its integration with Lidar in highly urbanized areas,IEEE Intelligent Transportation Systems Magazine,vol.12,no.3,pp.53-69,2020.19 C.Forster,L.Carlone,F.Dellaert,and D.Scaramuzza,On-manifold preintegration for real-time visual-inertial odometry,IEEE Transactions on Robotics,vol.33,no.1,pp.1-21,2016.20 J.Zhang and S.Singh,LOAM:Lidar odometry and mapping in real-time,in Robotics:Science and Systems,2014,vol.2,no.9.21 F.Dellaert and M.Kaess,Factor graphs for robot perception,Foundations Trends in Robotics,vol.6,no.1-2,pp.1-139,2017.22 Z.Zhang,Parameter estimation techniques:a tutorial with application to conic fitting,Image vision Computing,vol.15,no.1,pp.59-76,1997.23 S.Agarwal and K.Mierle.Ceres Solver.http:/ceres-solver.org(accessed 6 January 2021).24 J.J.Mor,The Levenberg-Marquardt algorithm:implementation and theory,in Numerical analysis:Springer,1978,pp.105-116.25 E.Kaplan and C.Hegarty,Understanding GPS:principles and applications.Artech house,2005.26 T.Takasu and A.Yasuda,Development of the low-cost RTK-GPS receiver with an open source program package RTKLIB,in International symposium on GPS/GNSS,2009:International Convention Center Jeju Korea,pp.4-6.27 A.M.Herrera,H.F.Suhandri,E.Realini,M.Reguzzoni,and M.C.de Lacy,goGPS:open-source MATLAB software,GPS Solution,vol.20,no.3,pp.595-603,2016.28 P.Teunissen,Theory of integer equivariant estimation with application to GNSS,Journal of Geodesy,vol.77,no.7-8,pp.402-410,2003.29 M.Quigley et al.,ROS:an open-source Robot Operating System,in ICRA workshop on open source software,2009,vol.3,no.3.2:Kobe,Japan,p.5.30 X.Bai,W.,Zhang,G.,Hsu,and Li-Ta,Real-time GNSS NLOS detection and correction aided by sky-pointing camera and 3D LiDAR,presented at the Proceedings of ION Pacific PNT 2019,Honolulu,HA,USA,2019.31 X.Bai,W.Wen,and L.-T.Hsu,Using Sky-pointing fish-eye camera and LiDAR to aid GNSS single-point positioning in urban canyons,IET Intelligent Transport Systems,vol.14,no.8,pp.908-914,2020.华为研究|1222022 年 12 月目前电视、电脑、手机、移动平板等显示设备的显示能力参差不齐，对于同一内容的显示效果不尽相同。常常会出现制作时的画面质量和终端呈现的画面质量不一致的情况，使消费者无法完全感知创作意图。为了缓解这一问题，创作者在创作时不得不做一些妥协；业界也制定了一些相关标准。尽管如此，消费者的体验和创作者想要表达的内容还是无法做到一致。为了解决这一难题，HDR（High Dynamic Range）Vivid 通过分析制作端作品内容的特征，生成元数据，基于这些元数据在终端侧根据人眼视觉系统的特性，结合终端的显示能力进行亮度、对比度、以及色彩感知保持的显示适配，从而最大限度还原创作意图。该技术通过优化色彩、亮度、对比度等画面要素，精准调色，从而呈现更卓越的视觉效果，并在不同的消费终端呈现出相似的创作意图，搭建了创作者和消费者之间的“桥梁”。关键词HDR，色调映射，视觉感知，亮度和对比度保存，质量控制，色彩感知，人眼感知模型，优化摘要余全合1，徐巍炜1，王弋川1，张继武1，陈虎2，袁乐31 中央媒体技术院2 慕尼黑音视频实验室3 上海海思信源技术开发部技术使能艺术：新一代 HDR Vivid视频技术标准123|华为研究2022 年 12 月软件技术与生态1 引言图 1 高质量影像要素高质量影像主要取决于以下五个要素：分辨率、位深度、帧速率、色域、动态范围。分辨率指数字图像中的像素数量 1。对于给定的显示设备尺寸，分辨率越高，所包含的像素越多，对细节的表现也就更加精细。国际电信联盟（International Telecommunication Union，ITU）发布的 BT.709 2 标准规定了高清影像的分辨率为 19201080。2012 年，ITU 又发布了 BT.2020 3 标准，将 4K（38402160）、8K（76804320）分辨率标准化。位深度表示每个像素可以显示的颜色比特数 4。位深越大，可显示的颜色数量就越多，整幅画面的渐变就越自然。BT.709 标准规定了高清影像的 8 bits 编码格式，为适应 4K/8K 影像要求，BT.2020 标准将位深提升到了10/12 bits。帧速率指单位时间（1s）内连续显示的图像的数量 5。电影的帧速率一般为 24p（每秒 24 帧）；BT.709 标准规定高清影像的最高帧速率为 60p；针对 8K 广播电视节目，BT.2020标准规定的最高帧速率可达120p，在该帧速率下，运动图像的平滑程度在视觉上几乎与真实世界无异。色域代表可以显示的所有颜色的范围合集 6。自然界中可见光谱的颜色组成了最大的色域空间，包含了人眼所能看到的所有颜色。显示设备的色域越大，能够再现的颜色就越多。BT.2020 标准相比 BT.709 标准，将色域从Rec.709 扩展到 Rec.2020，进一步扩大了颜色范围。动态范围指某一事物最大值与最小值之间的差异，比例关系是其中的一种体现方式 7。在影像领域，动态范围即是亮度的差别。动态范围越大，图像上同时记录的亮部细节与暗部细节就越丰富，给观看者的感受会更加真实。BT.2020 标准大幅推动了以上四个要素的发展，但在动态范围上并没有给出提升的建议。直到 2016 年，ITU 推出的 BT.2100 8 标准才正式定义了高动态范围（High Dynamic Range，HDR）影像的相关参数。HDR 技术的发展对显示终端的能力提出了更高的要求。根据 UHD 联盟针对电视机等终端设备认证提出的UltraHD Premium 标准 9，以亮度要求为例，若需通过HDR 认证，显示设备亮度特性需要满足以下要求：最大峰值亮度达到 1000 nits（cd/m2），最大黑度值（屏幕能够表现的仅次于关闭状态的最暗的亮度）不超过 0.05 nits（cd/m2）；或者，最大峰值亮度达到 540 nits（cd/m2），最大黑度值不超过 0.0005 nits（cd/m2）。然而，创作者制作的高质量 HDR 影像往往具有更大的动态范围。如何让它们能够在更低动态范围的显示设备上正确显示，同时忠实地还原创作者的意图，成为了需要解决的问题。降低动态范围的同时尽量保持原始影像对比度、细节等特征的过程被称为色调映射（Tone Mapping）10。学术界早在多年前就开始对色调映射算法进行研究。Reinhard 11 基于人眼视锥细胞的光感受响应，构建出全局色调映射算子；Kim 12 基于人类视觉灵敏度，提出遵循高斯分布并取决于场景的平均对数亮度映射模型；随着人工智能的发展，深度学习技术也被应用在色调映射研究中。Patel 13 利用生成对抗网络，进行有监督的色调映射学习。Zhang 14 采用多尺度的卷积神经网络，使得HDR 图像的全局信息与局部信息在映射过程中均得以最大程度的保留。为了进一步提升终端显示质量，工程实践与标准化过程中进一步采用“元数据”的概念，元数据包含了原始影像的特征信息，传输到显示端后，再根据相应的标准规范，指导终端基于元数据进行色调映射。电影电视工程 师 协 会（Society of Motion Picture and Television Engineers，SMPTE）于 2014 年颁布了 ST 2086 标准15，对 HDR 的静态元数据进行了规定。静态元数据包含了艺术家在调色时使用的监视设备的信息。本文提出的 HDR Vivid 技术与传统技术相比，其创新性主要体现在以下几个方面：1.采用高分辨率、宽位深、高帧率、广色域、高动态范围的策略，制作高质量的 HDR Vivid 内容。2.提出了一种亮度对比度和色彩保持方法，保证 HDR 内容的灵活性，稳定性和合理性，精确还原各种场景下的亮度对比度和色彩。3.采用动态元数据方案，结合人眼感知，确保 HDR 内容在具有不同显示能力的终端设备上均可以得到较为一致的呈现效果。4.借助内容生成制作工具，开放动态元数据的调整接口，从而给予创作者更大的艺术创作空间。华为研究|1242022 年 12 月HDR Vivid 相关技术已经被中国超高清视频产业联盟采纳，并成为高动态范围视频技术标准，本文将对 HDR Vivid 涉及的科学原理和技术方案做详细介绍。2.1 视觉艺术与 HDR 制作2.2 HDR 分发2 端到端 HDR 系统创作者通常利用现代技术创作作品，整个创作过程主要包括制作、分发和显示与感知。图 2 端到端 HDR 系统视觉艺术是指运用一定的物质、材料、技术手法，创作可供人观看欣赏的艺术作品。从广义上说，雕塑、绘画、摄影等艺术门类都属于它的范畴，它不仅创作方式多样，造型手法也十分多样 16。视觉艺术作为一种传达信息的“语言”，由视觉基本元素和设计原则两部分构成的一套传达意义的规范或符号系统 17。基本元素包括：线条、形状、明暗、色彩、质感、空间。艺术家通过组织和运用这些基本元素实现创作意图。艺术家根据需要选择相应的材料和表现形式（雕塑或是绘画、具象或是抽象等等），运用一定的原则和方法，在一定的范围内控制各种元素之间的关系，最后形成能够传达特定信息的图像 18。绘画是一种古老的视觉艺术 19，其发展受到技术的限制。洞穴人利用土系颜料制作洞穴壁画；文艺复兴时期从天青石中提取得到明亮的深蓝色颜料，使得该时期的圣母像呈现出高雅的蓝色；十九世纪新型色素井喷式的发展以及金属管的发明，为画家们带来了出门绘画的可能性与便捷性，带来了绘画史上的外光写生的发展。小孔成像的引入使绘画的逼真感大幅提升 20,21，同时也推动了十九世纪摄影的诞生。摄影随着盖达尔的银版摄影术诞生。1889 年，美国依斯曼柯达公司以硝化纤维素软片作为基材，大规模生产照相胶卷，推动了照相机的小型化。胶片利用银盐颗粒感光，银盐感光颗粒的光学特性近似于 Gamma 曲线 22。根据相纸的感光特性，辅以增厚剂和减薄剂，使用光谱特性狭窄的相纸等等才能获得满意的照片 23。二十世纪末，数码相机的发明使摄影技术的发展进入了新的阶段。根据摄影师 24测试，胶片相机可接受的宽容度为 8，而数码相机可接受的宽容度有 9，在很多情况下胶片的噪声和细节很难分辨，而数码相机的表现更好。从固定的石壁，到雕塑、绘画，再到电子显示设备，技术的发展深刻地改变了人创造和感知视觉艺术的方式。阴极射线管（Cathode Ray Tube，CRT）是广泛使用的电子显示设备，其使用的 P22 荧光粉色域接近 BT.709，最高亮度接近 100 nits。后来，液晶显示器（Liquid Crystal Display，LCD）快速发展，替代了 CRT，提供了更宽的色域范围以及更高的亮度 25。近年的 OLED（Organic Light-Emitting Diode）和 micro-LED 以及激光显示更是将色域表现拓展至 DCI-P3（Digital Cinema Initiative-P3）甚至 BT.2020，峰值亮度提升至 300010000 nits，显示位深提升至 10 bits。就像是矿物颜料提纯技术的发展促进了绘画的发展，HDR 技术的发展也来了更好感知体验。HDR Vivid 支持 12 bits、400010000 nits 的动态范围、BT.2020 色域（BT.2020 基本包络了视觉系统可感知的颜色范围）以及元数据控制，为艺术创作带来了更大的空间，为艺术的呈现带来了更灵活的手段。为了将 HDR 制作的作品进行有效分发，需要考虑合理的编码方式，其中位深度和线性到非线性转换是两个最重要因素。由于数字影像是离散的，为了保留更多、更细腻的信息，最简单的方式就是增加位深。在最大亮度不变的情况下，BT.2020 标准使用 10/12 bits 编码，记录的信息比BT.709 标准使用的 8 bits 要丰富得多。此外，对原始 HDR 内容最直观的编码方式是采用线性编码，但人类视觉感知系统并非是线性的，这种编码方式会造成亮部占用色阶过多，而暗部信息记录不足，不利于被人类视觉系统所感知。在视频领域，Gamma 输入输出特性曲线除了指代 CRT 显示器时代的“伽玛校正”，还有更为广泛的含义。采集端光传感器对所记录数据的转换称为光-电转换函数（Opto-electronic Transfer Function，OETF），而编码的数据在显示端被还原并显示出来的转 换 称 为 电-光 转 换 函 数（Electro-optical Transfer Function,EOTF）。任何类型的 OETF 与对应的 EOTF曲线均可被认为是广义上的伽玛曲线。然而应该设计什么样的 Gamma 曲线才能够符合人类视觉感知呢？学术界对此有相当多的研究与成果。整个 HDR 创作过程如图 2 所示。首先，创作者使用摄像机和调色软件等工具制作出母版；然后，分发过程将母版进行压缩和传输，形成压缩码流；最后，显示和感知过程将压缩码流进行解码和显示。这三个过程相互联系，每个过程的效果都会影响下一个过程。下面将对视觉艺术和 HDR制作